TopCoder

Caido
Waimai

User's AC Ratio

25.9% (7/27)

Submission's AC Ratio

22.7% (22/97)

Tags

Description

今年的臺大電資學院二階筆試考題有一題是這樣的:

130 的數字各一個,有多少種選 3 個數字的方法使得總和是 30 的倍數?

想當然耳,不太會數學的 FHVirus 當然沒有成功做出正確答案。為了復仇,他決定在校內賽出一題這樣的題目來搞你:

1N 的數字各一個,有多少種選 K 個數字的方法使得總和是 N 的倍數?

Input Format

第一行有一個數 T ,接下來有 T 行,每行有兩個整數 N,K ,意義如題敘所述。

保證對於所有的測資, 1KN109,K100

Output Format

對於每一組 (N,K) ,輸出一個整數,代表答案模 109+7 的餘數。

Sample Input 1

6
10 1
20 2
30 3
40 4
998244353 71
7122 19

Sample Output 1

1
9
136
2289
26337995
634802955

Hints

特別注意,儘管範測會不會過也可以拿到一些分數。

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 1~3 K=1 1
3 4~6 K=2 2
4 7~9 K=3,N500 3
5 10~12 K=4,N100 4
6 7~9, 13~15 K=3,N3000 5
7 7~9, 13~18 K=3 6
8 10~12, 19~21 K=4,N3000 10
9 7~15, 19~24 N3000 28
10 0~29 無額外限制 41

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536 1 10
1 1000 262144 65536 2 10
2 1000 262144 65536 2 10
3 1000 262144 65536 2 10
4 1000 262144 65536 3 10
5 1000 262144 65536 3 10
6 1000 262144 65536 3 10
7 1000 262144 65536 4 6 7 9 10
8 1000 262144 65536 4 6 7 9 10
9 1000 262144 65536 4 6 7 9 10
10 1000 262144 65536 5 8 9 10
11 1000 262144 65536 5 8 9 10
12 1000 262144 65536 5 8 9 10
13 1000 262144 65536 6 7 9 10
14 1000 262144 65536 6 7 9 10
15 1000 262144 65536 6 7 9 10
16 1000 262144 65536 7 10
17 1000 262144 65536 7 10
18 1000 262144 65536 7 10
19 1000 262144 65536 8 9 10
20 1000 262144 65536 8 9 10
21 1000 262144 65536 8 9 10
22 1000 262144 65536 9 10
23 1000 262144 65536 9 10
24 1000 262144 65536 9 10
25 1000 262144 65536 10
26 1000 262144 65536 10
27 1000 262144 65536 10
28 1000 262144 65536 10
29 1000 262144 65536 10