# EOJ Test Round #7

D. Binomial

Given $n$, $m$, $p$, output $\binom{n}{m} \bmod p$.

### 输入格式

In the first line are two integers $T$ and $p$ ($1 \le T \le 10^6, 1 \le p \le 10^9$, $p$ is prime), meaning the test case number and the prime $p$, respectively.

Next $T$ lines each contains 2 integers $n$ and $m$ ($1 \le n, m \le 10^9$).

### 输出格式

For each test case, output the binomial modulo $p$.

Input
4 7
4 2
2 1
1 1
5 3
Output
6
2
1
3

NaN