給n,m,k，求有多少對(i,j)滿足1 ≤ i ≤ n,0 ≤ j ≤ min(i,m)且Cij ≡ 0(mod k)，k 是質(zhì)數(shù)。其中 Cij 是組合數(shù)，表示從 i 個不同的數(shù)中選出 j 個組成 一個集合的方案數(shù)。
第一行兩個數(shù) t, k，其中 t 代表該測試點包含 t 組詢問，k 的意思與上文中 相同。
接下來 t 行每行兩個整數(shù) n, m，表示一組詢問。
(n,m ≤ 1018, t ≤ 105 )
輸出 t 行，每行一個整數(shù)表示對應(yīng)的答案。由于答案可能很大，請輸出答 案除以 109 + 7 的余數(shù)。
1 2 3 3
1