P8688 [Lanqiao Cup 2019 NOI Qualifier A] Binomial Coefficient Problem

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.

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 $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$.

**[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