The binomial coefficient $C_n^m$ represents the number of ways to choose $m$ items from $n$ items. For example, choosing two items from the three items $(1, 2, 3)$ can be done in three ways: $(1, 2), (1, 3), (2, 3)$. According to the definition of binomial coefficients, we can provide the general formula for calculating $C_n^m$:

$$C_n^m=\frac{n!}{m!(n-m)!}$$

where $n!=1\times2\times\cdots\times n$. (Additionally, $n!=1$ when $n=0$.)

Xiao Cong wants to know, given $n, m,$ and $k$, how many pairs $(i, j)$ satisfy $0\leq i\leq n$ and $0\leq j\leq \min(i, m)$ such that $C_i^j$ is a multiple of $k$.

The answer should be taken modulo $10^9 + 7$.

Input

The first line contains two integers $t$ and $k$, where $t$ represents the total number of test cases.

Each of the next $t$ lines contains two integers $n$ and $m$.

Output

Output $t$ lines, each containing an integer representing the number of pairs $(i, j)$ such that $0\leq i\leq n$ and $0\leq j\leq \min(i, m)$ where $C_i^j$ is a multiple of $k$.

Examples

Input 1

1 2
3 3

Output 1

1

Note 1

Among all possible cases, only $C_2^1=2$ is a multiple of $2$.

Input 2

2 5
4 5
6 7

Output 2

0
7

Input 3

3 23
23333333 23333333
233333333 233333333
2333333333 2333333333

Output 3

851883128
959557926
680723120

Constraints

For $20\%$ of the test cases, $1\leq n, m\leq 100$;

For another $15\%$ of the test cases, $n\leq m$;

For another $15\%$ of the test cases, $k=2$;

For another $15\%$ of the test cases, $m\leq 10$;

For $100\%$ of the test cases, $1\leq n, m\leq 10^{18}, 1 \leq t, k\leq 100$, and $k$ is a prime number.