P8688 [蓝桥杯 2019 省 A] 组合数问题

给 $n,m,k$，求有多少对 $(i,j)$ 满足 $1 \le i \le n,0 \le j \le \min(i,m)$ 且 ${i\choose j} \equiv 0\pmod{k}$，$k$ 是质数。其中 ${i\choose j}$ 是组合数，表示从 $i$ 个不同的数中选出 $j$ 个组成一个集合的方案数。

第一行两个数 $t,k$，其中 $t$ 代表该测试点包含 $t$ 组询问，$k$ 的意思与上文中相同。 接下来 $t$ 行每行两个整数 $n,m$，表示一组询问。

输出 $t$ 行，每行一个整数表示对应的答案。由于答案可能很大，请输出答案除以 $10^9+7$ 的余数。

**【样例说明】** 在所有可能的情况中，只有 ${2 \choose 1}=2$ 是 $2$ 的倍数。 **【数据规模和约定】** 对于所有评测用例，$1 \le k \le 10^8,1 \le t \le 10^5,1 \le n,m \le 10^{18}$，且 $k$ 是质数。 评测时将使用 $10$ 个评测用例测试你的程序，每个评测用例的限制如下：  蓝桥杯 2019 年省赛 A 组 J 题。