M. Random Variables
time limit per test
2 s
memory limit per test
64 megabytes
input
standard input
output
standard output

There are $$$n$$$ random variables. Each of them is chosen uniformly at random from $$$[1, m] \cap \mathbb{Z}$$$.

Let $$$occ_i$$$, where $$$i\in [1,m] \cap \mathbb{Z}$$$, denote the number of times the value $$$i$$$ occurs among the $$$n$$$ variables. Let $$$M=\max \{occ_i|i\in [1,m] \cap\mathbb{Z}\}$$$ .

For example, if $$$n=5,m=5$$$, the variables can be $$$\{4,4,3,1,5\}$$$ with probability $$$\frac{1}{3125}$$$. We have $$$occ_1=1$$$, $$$occ_2=0$$$, $$$occ_3=1$$$, $$$occ_4=2$$$, $$$occ_5=1$$$, $$$M=\max\{1,0,1,2,1\}=2$$$.

Now you're given $$$n$$$ and $$$m$$$; please work out the expected value of $$$M$$$. For convenience, let's denote the answer as $$$\mathrm E(M)$$$, then you only need to output $$$\mathrm E(M)\times m^n$$$ modulo $$$p$$$.

Input

The first line contains two positive integers $$$T$$$ and $$$p$$$ ($$$1\leq T\leq 10^4$$$, $$$2\leq p\leq 10^9+7$$$) — the number of test cases and the modulus.

The following $$$T$$$ lines each contain two positive integers $$$n$$$ and $$$m$$$ ($$$1\leq n\leq 1000$$$, $$$1\leq m\leq 10^9$$$) — the number of random variables and the upper bound of each random variable.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^4$$$.

Output

For each test case, print one line, a single integer — $$$\mathrm E(M) \times m^n$$$ modulo $$$p$$$.

Example
Input
3 123456789
3 2
5 5
7 7
Output
18
7145
2066323
Note

In the first test case, for results $$$\{1,1,2\}, \{1,2,1\}, \{1,2,2\}, \{2,1,1\}, \{2,1,2\}, \{2,2,1\}$$$, $$$M$$$ equals $$$2$$$; for results $$$\{1,1,1\}, \{2,2,2\}$$$, $$$M$$$ equals $$$3$$$. So, the total result is $$$1\times 0+2\times 6+3\times 2=18$$$, which equals $$$18$$$ modulo $$$123456789$$$ .