TopCoder

Thumb ezgif 4 d8e4e092c835
$nA-NIl$
$TIOJ 2046 送 107 次 TLE 的卡 judge 廢物$

User's AC Ratio

100.0% (17/17)

Submission's AC Ratio

78.9% (30/38)

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

No. Testdata Range Score
1 0~5 30
2 0~9 70

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1 2
1 1000 65536 262144 1 2
2 1000 65536 262144 1 2
3 1000 65536 262144 1 2
4 1000 65536 262144 1 2
5 1000 65536 262144 1 2
6 1000 65536 262144 2
7 1000 65536 262144 2
8 1000 65536 262144 2
9 1000 65536 262144 2