Description

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)$, and $(2,3)$. According to the definition of binomial coefficients, we have the general formula to compute $C_n^m$:

Here, $n!=1×2×⋯×n$. (In addition, when $n=0$, $n!=1$.)

Xiaocong wants to know: given $n$, $m$, and $k$, among all $0 \le i \le n$ and $0 \le j \le \min(i,m)$, how many pairs $(i,j)$ satisfy that $C_i^j$ is a multiple of $k$.

Output the answer modulo $10^9+7$.

Input Format

The first line contains two integers $t,k$, where $t$ is the total number of groups of testdata in this test point.

In the next $t$ lines, each line contains two integers $n,m$.

Output Format

Output $t$ lines. Each line contains one integer: among all $0 \le i \le n$ and $0 \le j \le \min(i,m)$, how many pairs $(i,j)$ satisfy that $C_i^j$ is a multiple of $k$.

1 2
3 3

1

2 5
4 5
6 7

0
7

3 23
23333333 23333333
233333333 233333333
2333333333 2333333333

851883128
959557926
680723120

Hint

Sample $1$ Explanation

Among all cases, only $C_{2}^{1}=2$ is a multiple of $2$.

Constraints and Notes

For $20\%$ of the test points, $1 \le n,m \le 100$.

For another $15\%$ of the test points, $n \le m$.

For another $15\%$ of the test points, $k=2$.

For another $15\%$ of the test points, $m \le 10$.

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

Translated by ChatGPT 5