User's AC Ratio

75.0% (3/4)

Submission's AC Ratio

66.7% (8/12)

Description

為了因應聖誕節,
因此玩偶工廠生產了許多聖誕節的相關玩偶,
有禮物玩偶、雪橇玩偶、馴鹿玩偶等,
但是主管在檢查的環節中發現某些玩偶有問題,
但是他只知道有問題的玩偶有哪些,
想問你有問題的那些產線可能的組合有幾種。

假設有 $n$ 種玩偶,其中 $k$ 種玩偶出問題,
則有問題的產線有 $\tbinom{n}{k}$ 種組合,
因此想請你計算出 $\tbinom{n}{k}$ 的值為多少。
由於數字很大,請輸出 $\tbinom{n}{k}$ 模 $M$ 之後的答案。

Input Format

第一行有兩個數字 $T,M$,分別代表測資數量與模數,
接下來 $T$ 行,每行有兩個數字 $n,k$,分別如題目所述。

  • $1\leq T\leq 2\times10^5$
  • $0\leq k\leq n\leq 10^5$
  • $10^5+1\leq M\leq 2\times 10^9$,$M$ 為質數

Output Format

對於每一組測資,請輸出一個數字代表 $\tbinom{n}{k}$ 模 $M$ 的值。

Sample Input 1

5 100003
10 6
8 3
10 3
9 7
2 0

Sample Output 1

210
56
120
36
1

Sample Input 2

10 1000000007
33 27
33 23
26 5
31 20
29 29
45 12
42 26
50 25
36 12
31 26

Sample Output 2

1107568
92561040
65780
84672315
1
760021549
509720440
605552882
251677693
169911

Hints

Problem Source

Subtasks

No. Testdata Range Score
1 0~17 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1
1 1000 65536 65536 1
2 1000 65536 65536 1
3 1000 65536 65536 1
4 1000 65536 65536 1
5 1000 65536 65536 1
6 1000 65536 65536 1
7 1000 65536 65536 1
8 1000 65536 65536 1
9 1000 65536 65536 1
10 1000 65536 65536 1
11 1000 65536 65536 1
12 1000 65536 65536 1
13 1000 65536 65536 1
14 1000 65536 65536 1
15 1000 65536 65536 1
16 1000 65536 65536 1
17 1000 65536 65536 1