题目描述

给 $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$，表示一组询问。

其中，$1≤k≤10^8,1≤t≤10^5,1≤n,m≤10^{18}$，且 $k$ 是质数。

输出描述

输出 $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

评测用例规模与约定：

对于 $20\%$ 的评测用例，$t \leq 1，n,m \leq 2000，k \leq 100$。

对于 $20\%$ 的评测用例，$t \leq 10^5，n,m \leq 2000，k \leq 100$。

对于 $30\%$ 的评测用例，$t \leq 100，n,m \leq 10^{18}，k \leq 100$。

对于 $30\%$ 的评测用例，$t \leq 10^5，n,m \leq 10^{18}，k \leq 10^8$。