시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 (추가 시간 없음) 512 MB0000.000%

문제

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.

예제 입력 1

3
2 2
4 3
10 2

예제 출력 1

12
447
14972

노트

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\}$.