Description

Given $n, m, k$, find how many pairs $(i, j)$ satisfy $1 \le i \le n$, $0 \le j \le \min(i, m)$, and ${i\choose j} \equiv 0\pmod{k}$, where $k$ is a prime number. Here ${i\choose j}$ is a binomial coefficient, which means the number of ways to choose $j$ elements from $i$ distinct elements to form a set.

Input Format

The first line contains two numbers $t, k$, where $t$ means this test point contains $t$ queries, and the meaning of $k$ is the same as above.

The next $t$ lines each contain two integers $n, m$, representing one query.

Output Format

Output $t$ lines, each line containing one integer representing the corresponding answer. Since the answer may be very large, output the remainder of the answer modulo $10^9+7$.

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 Explanation]

Among all possible cases, only ${2 \choose 1} = 2$ is a multiple of $2$.

[Constraints]

For all test cases, $1 \le k \le 10^8$, $1 \le t \le 10^5$, $1 \le n, m \le 10^{18}$, and $k$ is a prime number.

During judging, $10$ test cases will be used to test your program. The limits for each test case are as follows:

Lanqiao Cup 2019 Provincial Contest A Group, Problem J.

Translated by ChatGPT 5