TopCoder

Caido
Waimai

User's AC Ratio

100.0% (24/24)

Submission's AC Ratio

83.0% (39/47)

Tags

Description

對質數P和整數1XP1 ,定義f(P,X,K)為從(1,2,,P1)中刪除X後得到的P2元集合中所有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,K1

Output Format

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

Sample Input 1

1 7
5 3

Sample Output 1

1

Sample Input 2

2 11
10 5
6 7

Sample Output 2

1
3

Sample Input 3

1 1000000007
30 60

Sample Output 3

384495340

Hints

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

第一組30分,Q=1,P20
第二組70分,Q105,P2×109

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 (VSS, 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