Joseph and the Amazing Technicolor Balls

Submit

Language is selected by the extension of the file. See the list of supported languages to know the extension of your language.

Problem

Joseph, the second youngest of twelve brothers, is an accomplished juggler. He juggles dazzling balls of many colors and has become a big success in a land of his own. The balls come in m different colors, and any two balls of the same color are indistinguishable. For each color c_i he has a_i balls available. In preparation for his final act of juggling n balls at once, he has asked an audience member to pick out the balls -- any balls will do.

Given [a_1, a_2, ..., a_m] and n, print the number of ways to select the balls.

-- mitchs

Options

exec is denied

no deadline, the server will not save your submission

Sample input:_

[5,10,15,20]
12
[14,35,7,60,43,32]
16
[37,35,7,8]
58
[35,38,32,21,31,14,34,21,39]
45
[28,1,39,33,39]
6
[37,44,13,55]
6
[14,14,10,23,47,59,37,31]
29
[6,4,1,2,3,6]
6
[12,6,5,2,12,11,8,9,11,7,2]
13
[50,59,56,64,34]
46
[23,3,55,24,5,28,24]
14
[50,17,59,41]
22
[2,48,25,31,1,58,15]
7
[36,3,35]
49
[14,1,50,50,38,19,32,60,13,45,16]
28
[41,60,17]
11
[18,22,16,4,15,20,38,2,18,12]
13
[33,27,39,46,8,14]
19
[48,54,44,19,17,12,52,4,39,25,47]
15
[21,62,21,23,20,20,53]
62
[3,20,5,13,19,15,1,20,3]
27
[33,1,1,9,21,53,22,6,52,7,18,46]
17
[22,13,26,22,18,36,32,33,10,2]
38
[14,40,35,7,38,18,18,21,20,40]
8
[28,10,10,11,22,18,5,10,23,31,21]
16
[23,14,45,18,43]
57
[6,4,12,1,12,5,9,9,8,11,7,4]
16
[22,29,3,17,17,32,13,22,11,11]
23
[3,3,2,3,2,3,2,1,3]
3
[9,36,58,24]
56
[6,13,2,15,9,4,6,8,17,1,6,12]
19
[9,9,7,18,12,27,25,3,6]
27
[34,39,3,12,4,58,57,35,27,30,6]
26
[6,2,8,7,7,7,4,4,1,7,6,5]
8
[40,59,14,16,12,48,48]
4
[27,43,51,59]
19
[7,55,42,2]
8
[19,21,23,29,17,22,26,19,31,22,13]
32
[32,11,17,59,27]
61
[24,40,9,43,22,26]
52
[12,1,45,4]
44
[44,10,27,49,46,49,14,21,22]
24
[10,24,1,26,12]
33
[19,28,26,20,24,27,2,22,13,14,25]
29
[25,1,3,1,18,22,16,24,4,9,2,23]
18
[57,7,7,10,40,29,17]
51
[14,23,26,22,28,21,6,58,62,13,59]
20
[25,17,38,35,59,61,43,20,51,50]
3
[19,61,19]
27
[2,6,26,13,48,40,14,33]
53
[32,60,1,6,31,22,57,34]
4
[3,7,7,1,2]
12
[3,2,24,19,3,18,12,9,6,7]
24
[24,6,4,1,10,3,9,8,18,14,9]
21
[17,13,10,21,8,2,8,22,19,22,22,6]
12
[9,23,22,16,11,19,24,25,5,28,7,24]
4
[28,14,8,18,25,8,25,13,13,18]
29
[27,4,9,9,15,22,11,10]
30
[49,41,48,19,2,60,57,60,36,46]
15
[3,16,8,2,2,19,21,10,11,15,25,27]
14
[63,50,14]
44
[27,7,1,2,9,24,9,7,13,39]
18
[19,22,2,61,11]
26
[9,59,32,27,19,18,41,53,32,57]
24
[61,43,39,48]
4
[10,17,30]
19
[28,49,50,64,9,15,26]
61
[54,43,22,41,12,58,21,15,14]
40
[28,23,46,18,13]
15
[5,25,17,8,13,8,33,12,35,12]
20
[14,17,10,25]
39
[62,18,61,9,36]
6
[36,31,23,57]
58
[35,32,45,53,9,17,8]
48
[64,52,27,56,48,62,13,17,47]
34
[12,18,57,5,26,49,16]
59
[19,35,36,16,25]
36
[20,22,2,17,16,15,19,16,18,24,8]
22
[28,2,3]
29
[24,19,58,34,35,46,62,64]
54
[33,61,42,52,56,31]
28
[6,2,6,2,5,7,2,2,2,3,7]
7
[2,5,7,8,4,1,5,3,4,6,3,5]
9
[26,43,41,48,38,6,10,47,2]
37
[28,20,24,15,6,12,28,19,16]
28
[7,31,23]
33
[32,2,22,64,29]
43
[62,23,41,18,48,17,25,11,15]
49
[14,8,1,15,12,4,6,13,6,6,5,15]
16
[18,8,36,9,20,49]
35
[1,4,2,8,7,4]
17
[48,44,39,14,18,63,51,19,51,47]
33
[46,36,30,16]
46
[24,55,59,10,64,12,43,28,54,40,62,59]
24
[18,49,50,42,15,43,26]
33
[3,1,1,2,2,1,3,1,1,1,1,1]
3
[3,22,14,26]
30
[18,24,1,11,11,15,15,24,20,14,15]
23
[26,23,3,6,27,3,16,19,14,15,28,4]
23
[1,23,16,24,40,21,27,8,1]
50
[35,36,12,11,24,5,61,27,51]
11
[21,12,50,39,33,43,17]
38
[1,19,6,30,22,12,5,36,35]
38
[35,32,59,19]
21
[19,18,33,5,13,25,20,30,26,17,2]
10
[17,46,25,46,6,39,43]
24
[29,7,31,23]
27
[34,29,27,36,28,19,7,45,41]
40
[2,46,54,64,16,49,11,5]
11
[5,14,7,2,21,11,19,17,7,1,9]
25
[17,19,22,21,11,18,8,43]
49
[21,22,16,33,32,29,21,23,20,17,11]
13
[29,26,31,6,21,60,59,23]
21
[11,10,20,15,13,10,9,17]
20
[18,34,3,5,49,29,50,23]
50
[37,22,50]
30
[9,56,20,34,64]
48
[14,13,29,30,1,34,1,28,19]
34
[56,35,52,18,28]
27
[48,35,41,36,25,36,25,15,5]
16
[57,12,40,28,51,59]
4
[41,51,7,25]
30
[31,31,10,64,59,32,10,31,8,46,6]
7
[21,33,38,29,19,15,3,15,35,27]
37
[7,55,47,25,62,18]
25
[11,13,10,9,12,15,11,19,8,15,5]
20
[47,57,45,53]
59
[64,22,45,39,34,33,35]
28
[37,25,48,3,48,45,53,39]
11
[32,2,3,32,26,5,23,11,25,11,16]
12
[2,49,32,4]
54
[45,10,35,29,55,7,20,29]
52
[5,50,63]
20
[9,33,21,39,34,45]
31
[1,1,3,1,2,2,1,3,3,2,2]
3
[7,2,60,47,52]
39
[6,14,15,34,38,14,12,27,27,8]
39
[26,39,39,5,46,43,46,14]
53
[23,26,4,27,4,13,31,25,33,3,31]
9
[1,1,45,50,30,39,43,40,10,60]
5
[7,12,18,23,47,14,48,34,23]
28
[13,56,6,11,37,12,27,63,45]
23
[20,21,50,34,9,15,50,14,5]
9
[14,2,1,5,6,6,24,30,32,21,27]
18
[4,60,21,18,21,45,12,64,20,60,57]
22
[55,27,25,47,6,9]
10
[15,51,39]
56
[1,30,11,59]
37
[17,48,41,6,61]
46
[25,11,43]
17
[25,55,41,52,24,45,59,13,11,30,10,31]
28
[16,22,60]
43
[4,5,1,2,4,4,2,3,2,2]
5
[12,12,6,6,5,11,13,17,18,4]
18
[4,60,25,32]
49
[21,1,43]
23
[23,41,7,46]
42
[39,37,50,54,64,11,61]
33
[13,21,20,59,58]
14
[58,39,39,46]
19
[10,45,10,23,36,61,61,12,2,56]
33
[2,6,17,2,6,16,6]
18
[52,51,42,49,63,59,34]
63
[48,27,35,5]
40
[2,6,1,3]
8
[21,6,1,52,59,50,1]
24
[18,17,31]
39
[43,48,13,48,45,11,32,13,8]
30
[14,6,30,25,10,10,52,4,42,27,35,20]
26
[59,25,50,16,42,50,17,37]
51
[38,24,21,28,36,10,19,28,18]
40
[11,9,10,6,9,17,4,3]
17
[5,32,7]
35
[20,42,15,5,49]
21
[5,1,7]
9
[18,9,6,16,8,16]
25
[30,25,5,8,27,14,4,18,22,31]
12
[11,19,8,22,1,33,18,24,27]
48
[22,17,15,37,20,3,36,40,40,22]
5
[45,12,51,26,61,51,50,3,44,18,63]
17
[42,4,55]
24
[14,62,63]
44
[14,5,17,5,11,17,11,10,8,1]
17
[3,2,1,2,3,2,1,1,2]
3
[21,26,11,27,14,11,3]
27
[25,8,10,15,14,36,30,5,36]
12
[35,32,60,33,45,46]
12
[23,18,39,16,10,26,10,12,5]
39
[17,45,22,14,60]
63
[31,54,3,13,56,40,20,57,15]
24
[44,7,36,21,12,13,2,43]
45
[17,12,11,9,12,6,4,20,17,16,22,8]
23
[29,54,5]
59
[7,49,4,63,47,18]
42
[41,50,8,50,42,3,41,61,10,31]
24
[45,35,30,14,18,2,37,41]
11
[9,29,47,39,18,34]
4
[19,28,55,7,10,36,52,62,34,60]
11
[55,18,50,16,2,8]
47
[61,10,11,34,23,10,23]
8

Sample output:

367
19056
1620
821265699
140
84
7633868
260
764951
228935
27959
2265
1072
98
216144852
78
382733
39375
3083938
63606851
2441411
8172021
567275850
24309
5116969
204875
7000560
20778256
153
8805
19122130
9757195
137772986
58395
210
1540
108
1454648976
178538
2109870
130
10290446
6010
377193687
6847598
6544788
28889938
220
334
39833773
294
142
8844898
14145491
1179090
1365
139556271
4499390
1013574
2827045
570
1680868
7951
37747193
35
162
44551194
326994776
3871
8838035
2416
210
22551
10740927
114183651
14686710
76688
43507972
11
404310668
237336
14259
113594
63335304
25271521
189
35923
1218434853
7338826
335595
669
439890375
12428
414024325
3121992
266
1230
47602114
148650875
59626319
74295
6019518
33708766
2020
164318
491904
2500
297216117
24633
38779810
102839954
1144055
1067760
837185
49561134
460
130970
11745902
30970
691712
126
3121
19447
629636590
115710
27341380
36836
1344442
28392
505855
464
157576798
111
309210
238
15620
988898164
175591765
87375
1572
26440863
7010309
24145
4854499
55984279
2946
625
719
83510
150
1637090937
391
1553
3576010
4010
44
5375
2966613
3059
1540
200767138
24716
118254738
4165
20
50948
306
41616345
660506628
256353799
329211806
198678
42
8647
9
73731
277275
197614120
1992
7291219
115
570
1553045
134
532841
122793
6188
148717735
226890
7356900
20996231
231094760
165
333640
26964465
25389
126
167739
226746
3003

Sample input:_

[18,43,1]
43
[25,27,34,32,3,39]
45
[39,30,50]
51
[48,22,61,1,40,24,20,64,44,47]
3
[14,18,22,13]
24
[6,1,23]
23
[12,13,33,39,2,5,34,11,29,29]
21
[13,48,13,11,45,23]
49
[41,28,42,23,48,14,13,64,52,36,13,53]
10
[9,11,35,13,5,20,55]
14
[58,64,54,25,15]
62
[18,2,19,4,2,3,14,8,9,17,4]
19
[5,3,1,2,2,5,9,6,8,4]
10
[19,47,17,54,53,22]
31
[47,54,45,6]
11
[23,6,54,42,35,60]
45
[20,1,25,15,25,7,10,11,3,23,13,5]
17
[41,28,2,55,28,56,23,58,25]
10
[1,1,10,27,9,25,34,31]
42
[12,26,28,5,20,39,12,14,2,22]
39
[49,42,56,48]
7
[17,28,39,31,1,29,4,24,37,4]
39
[41,62,4,20,53,56,12,17,5,60,23]
21
[14,31,11,6,17,8,7,3,36]
36
[13,9,12,10,13,17,7,5,11,7,18,10]
19
[62,14,23,16,23]
15
[5,10,3,13,3,11,7,10,11,6,12]
14
[31,41,32,51]
63
[1,2,1,1,2]
3
[48,32,15,1,7,3,41,34,23]
5
[5,16,26,13,11,25,14,25,24,11,20,19]
27
[25,12,33]
62
[17,55,62,12,9,60,15]
14
[5,1,19,15,13,26,24,28,24,20,10,5]
15
[58,46,30,60,1,12,58,3,37]
38
[25,15,29,14,24,26,35,32]
46
[41,41,60]
11
[36,25,44,36,42,50,16,25]
55
[22,4,31,19,31,37,30,9,19,15]
40
[25,40,18,39,30,1,31,43,42]
20
[2,19,11,10,12,10,18,9]
21
[9,9,31,43,10,29]
12
[46,41,20]
8
[9,10,15,56,11,30,28,6,6]
45
[10,39,13,32,13,29]
11
[21,32,26,23,8,57,59,61,33,40,26]
26
[37,10,21,13]
60
[1,3,4,1,3,4,3,4,2,1,2,1]
4
[52,54,37]
47
[11,10,13,3,3,4,11,14,13,1,9,5]
16
[8,4,2,5]
9
[40,40,52,13,10,5,17]
42
[11,2,8,12,7,23,12,10,1,11]
25
[11,13,16,10,4,17,8,16,14,9,5,10]
17
[8,3,10,18,21,2,25,11,14,16,2,14]
23
[6,3,10,9,1,6,1,8,1,2]
11
[12,44,58,4,24,32]
61
[12,39,29,19,37,9,46,30,37]
30
[19,30,17]
35
[45,33,33]
35
[3,2,2,13,10]
15
[23,17,12]
35
[13,7,49,27,42,38,9,39,55]
22
[18,19,19,12,5,17,13,6,1,16]
20
[52,21,53,62,50]
46
[22,17,17,43,2,43,60,60,50,50]
4
[30,39,38,37,10,18,5,23,27]
7
[2,7,2,12,3,6]
12
[16,22,20,40,54,14,36,64,26]
3
[34,39,2,1,47,19]
62
[18,15,56,53,22]
34
[54,54,3,52,61]
28
[27,42,20,16,15,40,34,48,38]
49
[8,39,9,21,48]
15
[11,17,7,3]
21
[38,9,64,33,46,48,44]
17
[7,2,1,12,13,13]
13
[12,40,41,23,47,2]
22
[15,28,41,6,15,9]
39
[12,45,39,22,2,48,30,37]
52
[14,16,28,6,24,17,26,11,17,11,22]
33
[53,21,26,54,32]
15
[50,7,30,40,39,54,30]
64
[48,38,3]
59
[32,5,25,35,26]
25
[48,33,51,17,12,21]
12
[8,24,14,3,9,31,33,14,37,30]
37
[32,4,41,10,7]
53
[36,51,29,43,48,57,52,30]
45
[19,26,2,11,28,15,11,21,1,28,30]
31
[49,27,17]
57
[18,31,14,39,4,30,33,25,32]
20
[7,13,6,15,12,7,12,1]
15
[3,22,26,45,17,64,21]
25
[40,57,16,31,63,15,63,54,11,41,45,7]
6
[33,58,54,22,46,32]
9
[4,7,31,4,25,20,5,21,22,30,6]
32
[41,2,41]
60
[2,26,28,6,5,10,14,13]
29
[53,7,37,26,43]
24
[8,58,39,2,58]
47
[34,8,32,21,3,11,25,17]
37
[14,2,27,22,6,7,16,24,1,12,18,7]
5
[36,61,60,14,11,60]
63
[15,50,22]
43
[7,17,34,13,54,6,13,43]
23
[42,50,6,17,4,46,47]
55
[12,8,4,3,11,12,1,3,2,3,13]
13
[48,42,42,41]
60
[59,15,25,57,8,10,26,33]
48
[30,23,45,33,55,21]
39
[10,37,18]
46
[38,50,42,49,26]
19
[13,50,24,54]
63
[1,6,25]
14
[47,1,10,16,15,1]
46
[18,44,15,6,37,16,18,6,31]
18
[39,38,36,4,22,59,56]
48
[23,36,11,18,64,28,17,18]
53
[16,37,62,32,37,55,1,51]
18
[41,1,40,45,61,60]
33
[6,19,31,53,48,48,22,42,16]
10
[20,50,54,34,24,8,57]
7
[20,13,32,24,13,40,36]
43
[6,58,64,38,53,49,37]
37
[45,35,11,39,18,6,29,48,4]
33
[21,9,40,9,40,36]
41
[22,26,1,16,17,14,14,14,16,21,23,23]
26
[54,64,56,40,45]
7
[7,25,6,36,21,43]
13
[22,31,21,57,49]
40
[4,57,34,11,64]
63
[23,31,10,23,2,4,2,18]
33
[22,13,29,13,4,5,17,38,5,28]
24
[49,9,61,23,34]
47
[58,55,31,41,38,34,12,18,46,59]
22
[36,26,36,10,26,21,3,5,15]
11
[3,1,2,1,2,3]
3
[35,25,43]
51
[44,34,8,23,3,58,58]
59
[8,2,3,11,19,15,1,16,3,19,6]
3
[31,19,13,7,11]
31
[10,3,7,12,15,15,2,14,10,6,10,3]
16
[35,24,59,26,54,51,24,24]
6
[9,28,51,26,31,50,25,13,59]
27
[3,50,61,10,28,47,4]
62
[60,49,17,2,23,32,63]
25
[17,39,14]
21
[37,3,51,4,34,44,26,51]
22
[15,46,35,9,29,39,28,46,26]
41
[8,8,10,9,6,9]
11
[64,8,38,14,15,55,13,19,57,55,1]
5
[54,34,47,52,23,29,46,10,26,62,41,1]
18
[47,58,55,56,15,59]
53
[6,15,35,50,36,13,8,51]
31
[49,58,13,11,5,22,52,28,22,43]
39
[4,21,27,19,10,7,25,24,2,9,1,8]
24
[31,20,1,19,18,8,2,26,30,18,20]
24
[4,10,20,1,23]
57
[3,4,5,1,8,5,7,8,4,10,8]
10
[45,32,54]
31
[55,49,1,58,63]
3
[50,32,15,37,45,41,43,6,39]
31
[34,16,50,15,31,5,18,37,46]
5
[21,5,22,7,15,5,28,17,19]
28
[24,57,36,28,34]
49
[48,4,25,3,23,13,5,30,41]
34
[13,12,4,5,4,12,19,21,17]
23
[18,44,27,16,48,44,43]
32
[36,15,19,16,43,33,47,28]
52
[17,10,18]
22
[48,29,39,52]
63
[7,6,7,11,1,6,10]
11
[44,21,14,38,51,6,40,21,10,32]
26
[8,26,18,12,17,32,13,32,33,25,31]
26
[5,2,3]
5
[8,4,8,7,2,5,9,6]
9
[50,24,9,50,55,6,50]
11
[20,26,23,63,3,54,48]
9
[5,1,6,1,6,2]
6
[56,6,16,51,29,53,19,47,45,5,22]
10
[7,7,4,3,5,2,1,4,4,2,5,6]
7
[3,8,8,4]
8
[13,31,26,5,2,25,32,24,32,32,30]
26
[48,56,27,53,44,48]
4
[4,4,3,2,1,1,5,4,4,3,3]
5
[19,34,49,26,62,9,33,15]
8
[2,8,14,29,8,8,13,27,20,20,6]
15
[9,18,14,28,17,4,8,3,27,28,31]
31
[8,6,4,3,13,10,7,11,3,3,18,17]
20
[27,56,57,14,1,61,39,6,43,43]
40
[61,56,33,51,50]
19
[1,56,27,42,37,57,43,39]
62
[25,46,41,35,17,48,23,35,30]
15
[20,14,9,5,3,12,21,5,27,28,16]
28
[14,2,8,6,15,4,8,3,12,8,14,2]
15
[8,31,38,23,25,34,17,13]
30
[62,34,21,63,62,19]
47
[10,5,7,14]
27
[10,24,31,20,35,49,20,7,19]
31

Sample output:

38
695552
1068
210
2359
14
8530387
1130905
352716
35518
409291
6044580
42820
362769
329
1100008
11300223
37323
2786542
460512686
120
211474525
35912733
38134054
50357880
3875
1530539
31932
18
1113
1054982135
45
38543
4956797
38646334
128329990
78
428790518
1135021436
1545821
630510
6140
45
197253234
4367
245749504
1618
1032
1121
5893297
85
4131651
10841764
19292635
102713183
36355
1380180
44676489
344
660
386
156
5394811
4470906
209825
705
6426
1525
165
132516
61259
15485
1445965464
3540
364
99231
2307
36686
310780
83200677
1553800615
3876
63617224
118
14896
6188
477987768
13401
133491293
248382308
468
2616496
82949
438527
12376
2002
482009689
72
1765805
15630
25381
12963163
3927
4330062
368
1602950
9068129
429330
35737
102916968
1042631
164
8855
15305
14
11968
1411552
11318132
235701509
235535
124950
43593
1716
10277890
4148662
47873442
643922
435816565
330
7854
121956
82825
1467218
23380985
131655
20111235
67868
42
855
12969485
274
20846
8016041
1716
22250910
5591271
358028
215
811496
375538407
4187
2717
21531939
3731196
8117831
1102329007
110570646
40624165
5
126614
528
30
50528004
1287
16629266
256844
28573213
4025601
2679075
264951071
173
35054
6852
62248692
243897939
12
9237
12159
4543
186
183469
24288
110
139470528
126
2341
6435
2558181
502434449
39972125
497395182
8855
199858287
490314
229426395
4252566
8817393
2249142
196
50487043

Ranking

Ruby _

Perl _

Python _

Python3 _

PARI/GP _

C _

Haskell _

Bash (builtins) _

gs2 _

goruby _

Language Ranking_

return to the top page