Problem Statement
If you spent some time in academia (or solved TCO21 round 1B), you should be familiar with the h-index.
The h-index is a fairly popular method of evaluating an author's scientific impact. The h-index of an author is defined as the maximum value h such that the given author has published at least h papers that have each been cited at least h times.
Professor Doofus has told you that he has published P papers, that his papers have a total of C citations, and that his h-index is exactly H.
You would like to determine which of his papers has how many citations. Count all valid options, and return that count modulo 1,000,000,007.
Two options are considered the same if one can be obtained from the other by changing the names of the papers. For example, one option might be the scenario in which the professor has one paper with 2 citations, two papers with 7 citations each, and one paper with 0 citations.
Definition
- Class:
- HIndexCounting
- Method:
- count
- Parameters:
- int, int, int
- Returns:
- int
- Method signature:
- int count(int P, int C, int H)
- (be sure your method is public)
Constraints
- P will be between 1 and 50, inclusive.
- C will be between 0 and 3000, inclusive.
- H will be between 0 and P, inclusive.
Examples
7
0
1
Returns: 0
Seven papers, no citations. It is impossible to have a positive h-index.
6
10
3
Returns: 2
In order to have h-index 3, the professor must have: either papers with 0, 0, 0, 3, 3, and 4 citations or papers with 0, 0, 1, 3, 3, 3 citations
5
13
1
Returns: 5
6
18
3
Returns: 101
5
1500
5
Returns: 677184648
The exact answer is 1,677,184,655. The returned number is this answer modulo 10^9 + 7.
1
1
0
Returns: 0
13
1
0
Returns: 0
1
0
0
Returns: 1
7
0
0
Returns: 1
1
0
1
Returns: 0
1
1
1
Returns: 1
1
147
1
Returns: 1
50
899
30
Returns: 0
50
900
30
Returns: 1
50
2992
1
Returns: 50
50
2969
2
Returns: 1787575
50
2901
3
Returns: 31383857
50
2940
5
Returns: 971382314
50
2972
7
Returns: 798317538
50
2954
17
Returns: 153580472
50
2929
22
Returns: 183548302
50
2930
23
Returns: 882286754
50
2966
25
Returns: 658247423
50
2965
26
Returns: 584964715
50
2945
27
Returns: 257780521
50
2956
28
Returns: 129043672
50
2930
30
Returns: 647767581
50
2904
31
Returns: 294363974
50
2971
33
Returns: 745975012
50
2947
36
Returns: 622106565
50
2991
37
Returns: 889502286
50
2988
40
Returns: 47677993
50
2945
43
Returns: 742481238
50
2976
50
Returns: 915126447
24
978
18
Returns: 735867384
49
1368
3
Returns: 567726510
9
37
6
Returns: 2
37
2658
17
Returns: 504053546
17
1930
11
Returns: 773101735
50
66
8
Returns: 5
25
491
22
Returns: 92
18
322
18
Returns: 0
37
1983
37
Returns: 382765986
22
358
19
Returns: 0
49
2484
34
Returns: 455105693
10
16
4
Returns: 1
19
1819
18
Returns: 334153998
3
306
1
Returns: 3
20
294
17
Returns: 33
30
2490
12
Returns: 390327437
19
296
17
Returns: 73
48
1687
41
Returns: 65
4
1418
2
Returns: 4241
30
724
28
Returns: 0
33
404
13
Returns: 515464977
11
101
10
Returns: 2
28
16
4
Returns: 1
3
1697
3
Returns: 238290
7
1083
3
Returns: 3345557
5
2096
2
Returns: 10453
34
170
13
Returns: 2
32
718
1
Returns: 32
12
84
9
Returns: 10
5
2918
5
Returns: 575228697
6
91
4
Returns: 45771
8
2245
5
Returns: 292401898
22
2253
8
Returns: 22704874
40
2306
18
Returns: 712732433
34
470
22
Returns: 0
29
203
14
Returns: 110
22
363
19
Returns: 5
11
1890
2
Returns: 51660
44
1781
30
Returns: 32147887
39
1179
34
Returns: 44161
48
1005
32
Returns: 0
25
1895
11
Returns: 514407468
4
7
1
Returns: 4
20
2295
18
Returns: 253525847
15
189
14
Returns: 0
19
323
18
Returns: 0
7
2134
6
Returns: 409120956
48
1445
38
Returns: 2
50
575
24
Returns: 0
46
421
14
Returns: 297469995
35
398
20
Returns: 0
37
382
24
Returns: 0
42
777
28
Returns: 0
25
1606
19
Returns: 21362339
43
320
18
Returns: 0
21
55
7
Returns: 65
45
407
20
Returns: 110
31
637
11
Returns: 552566577
40
113
31
Returns: 0
30
785
28
Returns: 2
31
397
20
Returns: 0
9
696
5
Returns: 738847268
30
120
11
Returns: 0
18
287
17
Returns: 0
38
9
2
Returns: 20
40
1523
39
Returns: 4
38
150
12
Returns: 65
5
2556
2
Returns: 12753
7
9
4
Returns: 0
17
2450
15
Returns: 472528914