给定 $n$ 和 $k$，计算长度为 $n$、字符集大小为 $k$ 的随机字符串的后缀自动机中顶点的期望数量。若答案为 $r$，请输出 $r \cdot k^n \pmod{10^9 + 7}$。
输入格式
第一行包含测试用例的数量 $T$。接下来的 $T$ 行，每行包含整数 $n$ 和 $k$ ($1 \le k \le n \le 40$)。输入中的所有测试用例均不相同。
输出格式
输出 $T$ 行，每行对应一个测试用例的答案。
样例
输入 1
3 2 2 4 3 10 2
输出 1
12 447 14972
说明
令 $S(s)$ 为字符串 $s$ 的所有子串集合。字符串 $s$ 的后缀自动机是一个最小的有向无环图，它包含一个指定的顶点 $v_0$ 以及对图 $G$ 中所有边赋予的字符映射 $l(e)$，并满足以下性质： $S(s) = \{l(e_1) \dots l(e_k) \mid (e_1, \dots, e_k) \text{ 是从 } v_0 \text{ 出发的一条路径}\}$。