组合数问题 ### 题目描述 给 $n,m,k$，求有多少对 $(i, j)$ 满足 $1 \leq i \leq n,0 \leq j \leq \min(i,m)$且 $\dbinom{j}{i} ≡ 0 (\mod k)，k$ 是质数。其中 $\dbinom{j}{i}$ 是组合数，表示从 $i$ 个不同的数中选出 $j$ 个组成 一个集合的方案数。 ### 输入描述 第一行两个数 $t,k$，其中 $t$ 代表该测试点包含 $t$ 组询问，$k$ 的意思与上文中相同。 接下来 $t$ 行每行两个整数 $n,m$，表示一组询问。 其中，$1 \leq k \leq 10^8,1 \leq t \leq 10^5,1 \leq n,m \leq 10^{18}$，且 $k$ 是质数。 ### 输出描述 输出 $t$ 行，每行一个整数表示对应的答案。由于答案可能很大，请输出答案除以 $10^9 + 7$ 的余数。 ### 输入输出样例 #### 示例 > 输入 ```txt 1 2 3 3 ``` > 输出 ```txt 1 ```