给n,m,k，求有多少对(i,j)满足1 ≤ i ≤ n,0 ≤ j ≤ min(i,m)且Cij ≡ 0(mod k)，k 是质数。其中 Cij 是组合数，表示从 i 个不同的数中选出 j 个组成 一个集合的方案数。
第一行两个数 t, k，其中 t 代表该测试点包含 t 组询问，k 的意思与上文中 相同。
接下来 t 行每行两个整数 n, m，表示一组询问。
(n,m ≤ 1018, t ≤ 105 )
输出 t 行，每行一个整数表示对应的答案。由于答案可能很大，请输出答 案除以 109 + 7 的余数。
1 2 3 3
1