Problem Description

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

\[ C_n^m = \dfrac{n!}{m!(n-m)!} \]

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

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

The answer should be taken modulo \( 10^9 + 7 \).

Input Format

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

Next, \( t \) lines each contain two integers \( n \) and \( m \).

Output Format

Output \( t \) lines, each containing a single integer representing the number of pairs \((i, j)\) for all \( 0 \leq i \leq n \) and \( 0 \leq j \leq \min(i, m) \) that satisfy \( C_i^j \) is a multiple of \( k \).

Sample Input and Output

Input Sample #1

1 2
3 3

Output Sample #1

1

Input Sample #2

2 5
4 5
6 7

Output Sample #2

0
7

Input Sample #3

3 23
23333333 23333333
233333333 233333333
2333333333 2333333333

Output Sample #3

851883128
959557926
680723120

Notes

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 \leq n, m \leq 100 \);

For another \( 15\% \) of the test points, \( n \leq m \);

For another \( 15\% \) of the test points, \( k = 2 \);

For another \( 15\% \) of the test points, \( m \leq 10 \);

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

见题面 Input 部分

见题面 Output 部分