题目描述

给 $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$ 的余数。

1 2
3 3

1

2 5
4 5
6 7

0
7

3 23
23333333 23333333
233333333 233333333
2333333333 2333333333

851883128
959557926
680723120

提示

【样例说明】

在所有可能的情况中，只有 ${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 题。