题目描述
给 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≤108,1≤t≤105,1≤n,m≤1018，且 k 是质数。
输出描述
输出 t 行，每行一个整数表示对应的答案。由于答案可能很大，请输出答案除以 109+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≤1，n,m≤2000，k≤100。
对于 20% 的评测用例，t≤105，n,m≤2000，k≤100。
对于 30% 的评测用例，t≤100，n,m≤1018，k≤100。
对于 30% 的评测用例，t≤105，n,m≤1018，k≤108。
