Problem 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 \( \binom{i}{j} \equiv 0 \pmod{k} \), where \( k \) is a prime number. Here, \( \binom{i}{j} \) represents the combination number, which is the number of ways to choose a set of \( j \) items from \( i \) distinct items.

Input Format

The first line contains two numbers \( t \) and \( k \), where \( t \) represents the number of queries in this test case, and \( k \) is the same as mentioned above.

The next \( t \) lines each contain two integers \( n \) and \( m \), representing a query.

Output Format

Output \( t \) lines, each containing an integer representing the corresponding answer. Since the answer may be very large, output the answer modulo \( 10^9 + 7 \).

Sample Input and Output

Sample Input #1

1 2
3 3

Sample Output #1

1

Sample Input #2

2 5
4 5
6 7

Sample Output #2

0
7

Sample Input #3

3 23
23333333 23333333
233333333 233333333
2333333333 2333333333

Sample Output #3

851883128
959557926
680723120

Notes

[Sample Explanation]

Among all possible cases, only \( \binom{2}{1} = 2 \) is a multiple of 2.

[Data Range and 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 evaluation, 10 test cases will be used to test your program, each with the following constraints:

This problem is the J题 from the 2019 Lanqiao Cup Provincial Competition, Group A.

见题面 Input 部分

见题面 Output 部分