P6669 [Tsinghua Training 2016] Binomial Coefficient Problem

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$: $$C_n^m=\dfrac{n!}{m!(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$.

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

#### 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