給n,m,k，求有多少對(duì)(i,j)滿足1 ≤ i ≤ n,0 ≤ j ≤ min(i,m)且Cij ≡ 0(mod k)，k 是質(zhì)數(shù)。其中 Cij 是組合數(shù)，表示從 i 個(gè)不同的數(shù)中選出 j 個(gè)組成 一個(gè)集合的方案數(shù)。
第一行兩個(gè)數(shù) t, k，其中 t 代表該測(cè)試點(diǎn)包含 t 組詢問(wèn)，k 的意思與上文中 相同。
接下來(lái) t 行每行兩個(gè)整數(shù) n, m，表示一組詢問(wèn)。
(n,m ≤ 1018, t ≤ 105 )
輸出 t 行，每行一個(gè)整數(shù)表示對(duì)應(yīng)的答案。由于答案可能很大，請(qǐng)輸出答 案除以 109 + 7 的余數(shù)。
1 2 3 3
1
全部藍(lán)橋杯真題，模擬訓(xùn)練，博客發(fā)布完整題解的同學(xué)有獎(jiǎng)勵(lì)哦！
預(yù)告：四月月賽為女生專場(chǎng)，趕緊預(yù)約你的女神！ C語(yǔ)言網(wǎng)只能幫單身的你幫到這了！