題目描述

魔法學院中，有n 位學生，學院要舉辦一場魔法對抗賽。教練想要從這n 位學生中選出m 位學生組成一
支代表隊，可是這樣有太多不同的方法了！現在有q 個詢問，每個詢問給定n 和m，請你計算出從n 位
學生中選出m 位學生組成一支代表隊，有多少種不同的選法？由於答案可能很大，請輸出結果對給定的
質數p 取模的值。

輸入格式

輸入格式
q p
n_1 m_1
n_2 m_2 ...
n_q m_q
其中：
• q 表示詢問的數量
• p 是一個質數，用於取模運算
• 接下來q 行，每行包含兩個整數n_i 和m_i

輸出格式

輸出格式
ans_1
ans_2 ...
ans_q
對於每個詢問，輸出一行表示選法的總數模p 的值。

Samples

3 11
5 2
7 3
17 4

10
2
4

提示

測支解釋

• 第一組n=5,m=2 有10 種選法：
{1,2,3},{1,2,4},{1,2,5},{1,3,4},{1,3,5},{1,4,5},{2,3,4},{2,3,5},{2,4,5},{3,4,5}
• 第二組n=7,m=3 有35 種選法，模11 餘2
• 第三組n=17,m=4 有2380 種選法，模11 餘4

約束條件
• 1 ≤ q ≤ 10_5
• 1 ≤ p ≤ 10_7，且p 是質數
• 0 ≤ m_i ≤ n_i ≤ 10^100
子任務
1.（20 分）p ≤ 100，n_i ≤ p，q ≤ 10
2.（20 分）p ≤ 100，n_i ≤ p^2，q ≤ 100
3.（20 分）p ≤ 1000，n_i ≤ p^3，q ≤ 1000
4.（20 分）p ≤ 10^6，n_i ≤ 10^18，q ≤ 10^5
5.（20 分）保證q ≤ 10^6/logp(n)，且p,q,n,m 符合約束條件。

原始資料

• Zero1 題號：b514
• Hydro 題號：Z1514
• Locale：en_US
• Display：open