23645번 - Automaton 다국어

Given $n$ and $k$, calculate the expected number of vertices in the suffix automaton of a random string of length $n$ over alphabet of size $k$. If $r$ is the answer, output $r\cdot k^n$ modulo $10^9 + 7$.

The first line contains the number of tests $T$. Each of the next $T$ lines contains integers $n$ and $k$ ($1 \le k \le n \le 40$). All tests in the input are different.

Output $T$ lines with answers for tests.

Let $S(s)$ be the set of all substrings of $s$. Suffix automaton of a string $s$ is the smallest directed acyclic graph with a specified vertex $v_0$ and an assignment $l(e)$ of characters to all edges of $G$ that satisfies the following property: $S(s) = \{l(e_1)\ldots l(e_k) \mid (e_1, \ldots, e_k)\text{ --- a path starting at }v_0\}$.