#### 问题描述
给 n, m, k， 求有多少对(i, j)满足 1 ≤ i ≤ n, 0 ≤ j ≤ min(i, m) 且$C_i^j$≡0(mod k)，k 是质数。其中$C_i^j$是组合数，表示从 i 个不同的数中选出 j 个组成一个集合的方案数。
#### 输入格式
第一行两个数 t, k，其中 t 代表该测试点包含 t 组询问，k 的意思与上文中相同。
接下来 t 行每行两个整数 n, m，表示一组询问。
#### 输出格式
输出 t 行，每行一个整数表示对应的答案。由于答案可能很大，请输出答案除以 109 + 7 的余数。
#### 样例输入
```
1 2
3 3
```
#### 样例输出
```
1
```
#### 样例说明
在所有可能的情况中，只有 $C_2^1$ 是 2 的倍数。
#### 样例输入
```
2 5
4 5
6 7
```
#### 样例输出
```
0
7
```
#### 样例输入
```
3 23
23333333 23333333
233333333 233333333
2333333333 2333333333
```
#### 样例输出
```
851883128
959557926
680723120
```
#### 数据规模和约定
```
对于所有评测用例，1 ≤ k ≤ 108, 1 ≤ t ≤ 105, 1 ≤ n, m ≤ 1018，且 k 是质数。评测时将使用 10 个评测用例测试你的程序
```