有 $n$ 个随机变量，每个变量都在 $[1, m] \cap \mathbb{Z}$ 中均匀随机选取。

令 $occ_i$（其中 $i \in [1, m] \cap \mathbb{Z}$）表示值 $i$ 在这 $n$ 个变量中出现的次数。令 $M = \max\{occ_i \mid i \in [1, m] \cap \mathbb{Z}\}$。

例如，若 $n = 5, m = 5$，变量取值可能为 $\{4, 4, 3, 1, 5\}$，其概率为 $\frac{1}{3125}$。此时 $occ_1 = 1, occ_2 = 0, occ_3 = 1, occ_4 = 2, occ_5 = 1$，则 $M = \max\{1, 0, 1, 2, 1\} = 2$。

现在给定 $n$ 和 $m$，请计算 $M$ 的期望值。为了方便起见，记答案为 $E(M)$，你只需要输出 $E(M) \times m^n \pmod p$ 的结果。

输入格式

第一行包含两个正整数 $T$ 和 $p$ ($1 \le T \le 10^4, 2 \le p \le 10^9 + 7$)，分别表示测试用例的数量和模数。

接下来的 $T$ 行，每行包含两个正整数 $n$ 和 $m$ ($1 \le n \le 1000, 1 \le m \le 10^9$)，分别表示随机变量的数量和每个随机变量的取值上限。

保证所有测试用例中 $n$ 的总和不超过 $10^4$。

输出格式

对于每个测试用例，输出一行，包含一个整数，即 $E(M) \times m^n \pmod p$。

样例

输入 1

3 123456789
3 2
5 5
7 7

输出 1

18
7145
2066323

说明

在第一个测试用例中，对于结果 $\{1, 1, 2\}, \{1, 2, 1\}, \{1, 2, 2\}, \{2, 1, 1\}, \{2, 1, 2\}, \{2, 2, 1\}$，$M$ 等于 $2$；对于结果 $\{1, 1, 1\}, \{2, 2, 2\}$，$M$ 等于 $3$。因此，总结果为 $1 \times 0 + 2 \times 6 + 3 \times 2 = 18$，即 $18 \pmod{123456789}$。