给n, m, k，求有多少对(i, j)满足1 ≤ i ≤ n, 0 ≤ j ≤ min(i, m)且Ci j ≡ 0(mod k)，k 是质数。其中Ci j是组合数，表示从i个不同的数中选出 j 个组成 一个集合的方案数。 输入：第一行两个数 t, k，其中 t 代表该测试点包含 t 组询问，k 的意思与上文中 相同。 接下来 t 行每行两个整数 n, m，表示一组询问。 输出：输出 t 行，每行一个整数表示对应的答案。由于答案可能很大，请输出答 案除以 10^9 + 7 的余数。 数据规模： 40%：1 ≤ k ≤ 100, 1 ≤ t ≤ 10^5, 1 ≤ n, m ≤ 2000 100%：1 ≤ k ≤ 10^8, 1 ≤ t ≤ 10^5, 1 ≤ n, m ≤ 10^18