Problem Statement
They soon realized that there are many ways of making the album. Two albums are considered different if there is a song that is sung by a different set of Vocaloids. Let X be the number of possible albums. Since the number X can be quite large, compute and return the number (X modulo 1,000,000,007).
Definition
- Class:
- VocaloidsAndSongs
- Method:
- count
- Parameters:
- int, int, int, int
- Returns:
- int
- Method signature:
- int count(int S, int gumi, int ia, int mayu)
- (be sure your method is public)
Constraints
- S will be between 1 and 50, inclusive.
- gumi, ia and mayu will be each between 1 and S, inclusive.
Examples
3
1
1
1
Returns: 6
In this case, there are 3 songs on the album. And Gumi, Ia, Mayu will each sing one song. There are 3*2*1 = 6 ways how to choose which Vocaloid sings which song.
3
3
1
1
Returns: 9
Gumi will sing all three songs. Ia and Mayu can each choose which one song they want to sing.
50
10
10
10
Returns: 0
It is not possible to record 50 songs if each Vocaloid can only sing 10 of them.
18
12
8
9
Returns: 81451692
50
25
25
25
Returns: 198591037
2
1
1
1
Returns: 6
2
2
2
1
Returns: 2
3
2
2
1
Returns: 21
3
2
2
2
Returns: 24
3
3
2
2
Returns: 9
3
3
3
3
Returns: 1
4
1
1
1
Returns: 0
4
2
2
1
Returns: 48
4
3
1
1
Returns: 28
4
3
2
1
Returns: 60
4
3
2
2
Returns: 108
4
3
3
1
Returns: 52
4
3
3
2
Returns: 84
4
3
3
3
Returns: 60
4
4
2
2
Returns: 36
4
4
3
1
Returns: 16
4
4
3
2
Returns: 24
4
4
3
3
Returns: 16
4
4
4
1
Returns: 4
4
4
4
2
Returns: 6
4
4
4
3
Returns: 4
4
4
4
4
Returns: 1
41
29
4
38
Returns: 369692696
36
20
2
33
Returns: 192664730
28
5
10
4
Returns: 0
14
6
7
10
Returns: 336213866
44
14
14
18
Returns: 745566248
32
17
23
9
Returns: 566625093
26
1
26
7
Returns: 17102800
37
17
25
31
Returns: 745634133
32
9
19
23
Returns: 377232929
41
22
8
8
Returns: 0
36
7
7
19
Returns: 0
44
4
37
20
Returns: 827379536
11
11
1
10
Returns: 121
45
18
1
26
Returns: 881039084
30
5
24
16
Returns: 75352941
3
3
2
2
Returns: 9
38
14
5
13
Returns: 0
16
9
2
3
Returns: 0
7
2
1
7
Returns: 147
18
14
2
14
Returns: 546060060
50
35
13
35
Returns: 34125268
50
44
41
6
Returns: 299345062
50
40
32
25
Returns: 966179195
50
22
22
28
Returns: 772146954
50
32
32
42
Returns: 379364574
50
9
17
5
Returns: 0
50
35
37
34
Returns: 598448803
50
46
17
8
Returns: 926765926
50
44
13
13
Returns: 719726720
50
9
50
47
Returns: 500176258
50
23
23
26
Returns: 921345188
48
48
1
1
Returns: 2304
10
5
6
7
Returns: 3087000
50
30
30
30
Returns: 828008844
34
33
32
31
Returns: 113546400
50
17
23
35
Returns: 265230684
50
25
47
32
Returns: 761655492
3
2
1
1
Returns: 15
50
20
1
49
Returns: 271477184
50
25
24
1
Returns: 138821945
50
13
23
34
Returns: 732797345
50
27
22
34
Returns: 219559533
50
25
24
25
Returns: 697128534