TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

100.0% (14/14)

Submission's AC Ratio

78.8% (26/33)

Description

對質數$P$和整數$1\leq X \leq P - 1$ ,定義$f(P,X,K)$為從$(1,2,\dots,P-1)$中刪除$X$後得到的$P-2$元集合中所有$K$元子集合的積的和。
例如$f(7,5,3)=260$。
因為$(1,2,3,4,6)$中的$3$元子集合有$(1,2,3),(1,2,4),(1,2,6),(1,3,4),(1,3,6),(1,4,6),(2,3,4),(2,3,6),(2,4,6),(3,4,6)$,
故$f(7,5,3)=6+8+12+12+18+24+24+36+48+72=260$
給定$P,X,K$請求出$f(P,X,K)$%$P$

Input Format

第一行有兩個正整數$Q, P$,代表測資筆數和給定的質數。
接下來每一筆測資中,有兩個非負整數$X,K\geq 1$

Output Format

對於每筆測資,輸出$f(P,X,K)$%$P$。

Sample Input

#Sample Input 1
1 7
5 3

#Sample Input 2
2 11
10 5
6 7

#Sample Input 3
1 1000000007
30 60

Sample Output

#Sample Output 1
1

#Sample Output 2
1
3

#Sample Output 3
384495340

Hints

本題共有兩組測試資料。每組可有多個輸入檔案,全部答對該組才得分。

第一組30分,$Q=1, P\leq 20$
第二組70分,$Q\leq 10^ 5,P\leq 2\times 10^ 9 $

Problem Source

rsabcmoi

Subtasks

For Testdata: 0 ~ 5, Score: 30
For Testdata: 0 ~ 9, Score: 70
No. Time Limit (ms) Memory Limit (KiB)
0 1000 65536
1 1000 65536
2 1000 65536
3 1000 65536
4 1000 65536
5 1000 65536
6 1000 65536
7 1000 65536
8 1000 65536
9 1000 65536