考虑一个大小为 $c$ 的字符集 $\sigma$。共有 $c^{2n}$ 个长度为 $2n$ 的字符串，其中每个字符都在 $\sigma$ 中。如果一个字符串的下标集合 $\{1, 2, \dots, 2n\}$ 可以被划分为 $n$ 个对，满足以下条件，则称该字符串为完美字符串：

• 每个下标恰好属于一个对。
• 对于每一对 $(i, j)$，满足 $S[i] = S[j]$。
• 任意两对不相交，即对于任意两对 $(i, j)$ 和 $(k, l)$，满足 $i < k < j < l$ 的情况一定不成立。

给定 $n$ 和 $c$，计算长度为 $2n$ 的完美字符串的数量，结果对 $10^9 + 7$ 取模。

输入格式

第一行包含一个整数 $T$，表示测试用例的数量。接下来是各个测试用例。 每个测试用例包含两个空格分隔的整数 $n$ 和 $c$。

数据范围

• $1 \le T \le 10^5$
• $1 \le n, c \le 10^7$
• 所有测试用例中 $n$ 的总和不超过 $10^7$。

样例

输入格式 1

2
3 1
2 2

输出格式 1

1
6

说明

在第一个测试用例中，只有一个字符串，且它显然是完美的。 在第二个测试用例中，设字符集为 $\{a, b\}$。完美字符串如下（附带其下标的配对划分）：

aaaa $\{(1, 4), (2, 3)\}$ aabb $\{(1, 2), (3, 4)\}$ abba $\{(1, 4), (2, 3)\}$ baab $\{(1, 4), (2, 3)\}$ bbaa $\{(1, 2), (3, 4)\}$ bbbb $\{(1, 2), (3, 4)\}$