553_A. Kyoya and Colored Balls_28657
Kyoya Ootori has a bag with n colored balls that are colored with k different colors. The colors are labeled from 1 to k. Balls of the same color are indistinguishable. He draws balls from the bag one by one until the bag is empty. He noticed that he drew the last ball of color i before drawing the last ball of color i + 1 for all i from 1 to k - 1. Now he wonders how many different ways this can happen. 

Input

The first line of input will have one integer k (1 ≤ k ≤ 1000) the number of colors.

Then, k lines will follow. The i-th line will contain ci, the number of balls of the i-th color (1 ≤ ci ≤ 1000).

The total number of balls doesn't exceed 1000.

Output

A single integer, the number of ways that Kyoya can draw the balls from the bag as described in the statement, modulo 1 000 000 007. 

Examples

Input

3
2
2
1


Output

3


Input

4
1
2
3
4


Output

1680

Note

In the first sample, we have 2 balls of color 1, 2 balls of color 2, and 1 ball of color 3. The three ways for Kyoya are: 
    
    
      
    1 2 1 2 3  
    1 1 2 2 3  
    2 1 1 2 3  
    
import java.io.*;
import java.util.*;
public class Competencia2 {
	public static void main(String[] args) {
		  int modulo = 1000000007;
		  int max = 1000;
		  Scanner scan = new Scanner(System.in);
		    
		  long[][] combinatoria = new long[max][max];
		  combinatoria[0][0] = 1;
		  for (int i = 1; i < max; i++) {
			  combinatoria[i][0] = 1;
			  	for (int j = 1; j <= i; j++) {
			  		combinatoria[i][j] = (combinatoria[i-1][j] + combinatoria[i-1][j-1]) % modulo;
			  	}
		    }
		    
		    int K = scan.nextInt();
		    int[] color = new int[K];
		    for (int i = 0; i < K; i++) color[i] = scan.nextInt();
		    
		    long res = 1;
		    int total = 0;
		    for (int i = 0; i < K; i++) {
		      res = (res * combinatoria[total + color[i] - 1][color[i] - 1]) % modulo;
		      total += color[i];
		    }
		    
		   System.out.println(res);
		   scan.close();
	}
}

4
1
2
3
4
 3
2
2
1
 1
5
 10
100
100
100
100
100
100
100
100
100
100
 25
35
43
38
33
47
44
40
36
41
42
33
30
49
42
62
39
40
35
43
31
42
46
42
34
33
 5
10
10
10
10
10
 1
1
 11
291
381
126
39
19
20
3
1
20
45
2
 13
67
75
76
80
69
86
75
86
81
84
73
72
76
 47
20
21
16
18
24
20
25
13
20
22
26
24
17
18
21
22
21
23
17
15
24
19
18
21
20
19
26
25
20
17
17
17
26
32
20
21
25
28
24
21
21
17
28
20
20
31
19
 3
343
317
337
 1
3
 25
35
43
38
33
47
44
40
36
41
42
33
30
49
42
36
39
40
35
43
31
42
46
42
34
33
 5
10
10
10
10
17
 11
291
381
126
39
23
20
3
1
20
45
2
 13
67
5
76
80
69
86
75
86
81
84
73
72
76
 4
1
2
3
2
 11
291
381
126
66
23
20
3
1
20
45
2
 13
67
5
76
80
69
86
61
86
81
84
73
72
76
 4
1
4
3
2
 11
291
381
126
66
23
20
6
1
20
45
2
 13
67
5
76
80
69
86
61
86
81
84
73
99
76
 4
1
4
6
2
 13
67
5
76
80
69
86
61
86
81
84
19
99
76
 4
1
4
6
3
 13
67
5
76
80
69
86
61
86
116
84
19
99
76
 4
1
3
6
3
 13
67
5
76
151
69
86
61
86
116
84
19
99
76
 13
67
5
76
151
69
33
61
86
116
84
19
99
76
 13
67
5
76
151
69
33
61
86
116
84
30
99
76
 25
35
43
38
33
47
44
40
36
41
42
33
30
49
42
62
39
40
35
43
31
42
46
42
34
13
 5
10
10
10
10
2
 11
166
381
126
39
19
20
3
1
20
45
2
 13
53
75
76
80
69
86
75
86
81
84
73
72
76
 3
318
317
337
 3
2
3
1
 25
35
43
38
33
47
44
40
52
41
42
33
30
49
42
36
39
40
35
43
31
42
46
42
34
33
 5
10
11
10
10
17
 11
291
381
36
39
23
20
3
1
20
45
2
 13
67
5
76
80
69
86
75
86
81
84
73
18
76
 4
1
2
2
2
 11
291
381
38
66
23
20
3
1
20
45
2
 13
67
5
76
80
69
86
61
86
81
84
36
72
76
 11
291
381
6
66
23
20
6
1
20
45
2
 13
67
5
76
80
69
51
61
86
81
84
73
99
76
 4
2
4
6
2
 13
67
5
76
80
20
86
61
86
81
84
19
99
76
 13
67
5
76
80
69
86
61
86
116
84
19
73
76
 4
1
5
6
3
 13
67
5
76
151
69
86
61
86
116
84
19
64
76
 13
67
5
76
151
69
33
91
86
116
84
19
99
76
 13
67
5
76
160
69
33
61
86
116
84
30
99
76
 25
35
43
38
33
47
55
40
36
41
42
33
30
49
42
62
39
40
35
43
31
42
46
42
34
13
 5
2
10
10
10
2
 11
166
381
126
39
19
20
3
1
30
45
2
 3
318
33
337
 3
2
6
1
 5
10
18
10
10
17
 11
291
381
36
48
23
20
3
1
20
45
2
 13
67
5
76
80
69
86
75
86
81
161
73
18
76
 4
2
2
2
2
 11
291
381
38
66
23
40
3
1
20
45
2
 13
67
5
76
80
69
86
61
86
81
84
37
72
76
 13
67
5
76
80
69
51
61
86
81
84
102
99
76
 4
2
3
6
2
 13
67
5
96
80
20
86
61
86
81
84
19
99
76
 13
67
5
35
80
69
86
61
86
116
84
19
73
76
 13
67
5
76
151
69
86
61
86
116
103
19
64
76
 13
67
5
76
151
69
33
91
86
129
84
19
99
76
 25
35
43
38
33
47
55
40
36
41
42
33
30
49
42
62
39
40
35
43
31
42
46
42
39
13
 5
2
4
10
10
2
 3
318
33
180
 3
2
10
1
 5
10
28
10
10
17
 11
291
381
3
48
23
20
3
1
20
45
2
 13
67
5
76
80
69
86
75
86
35
161
73
18
76
 4
2
2
4
2
 11
291
381
16
66
23
40
3
1
20
45
2
 13
31
5
76
80
69
86
61
86
81
84
37
72
76
 13
67
5
76
80
69
51
61
86
81
84
102
99
93
 4
2
6
6
2
 13
68
5
96
80
20
86
61
86
81
84
19
99
76
 13
67
5
35
80
69
138
61
86
116
84
19
73
76
 13
67
5
76
151
69
86
61
86
116
103
19
64
50
 25
35
43
38
33
47
55
40
36
41
42
33
30
49
42
62
39
40
35
43
21
42
46
42
39
13
 5
2
4
12
10
2
 3
305
33
180
 3
2
10
2
 5
10
28
10
10
15
 3
2
1
1
 1
2
 1
4
 1
6
 1
7

1680
 3
 1
 12520708
 362689152
 425711769
 1
 902382672
 232242896
 295545118
 691446102
 1
 997961972
 741776646
 561962362
 872636499
 140
 957968984
 882010690
 756
 734734213
 248017518
 12096
 67616577
 78624
 906113884
 24948
 410366722
 200911746
 864842422
 78820644
 75782637
 236575578
 269600365
 462623218
 6
 15644367
 200406298
 215626521
 231144888
 48
 296218359
 69577029
 566019161
 667966130
 60060
 395962938
 868686169
 210210
 571867598
 864580062
 398529333
 289252420
 207935858
 71126029
 794427986
 21
 237550644
 33733705
 295312122
 105
 776448978
 421970440
 986468588
 18144
 699726491
 238112626
 988951103
 656673519
 795647390
 774246930
 609120060
 55
 900560572
 526774893
 579369431
 945
 75386802
 839484998
 106624056
 405405
 53320218
 486830189
 699384957
 451426514
 202280253
 59672446
 715
 645711692
 1
 1
 1
 1
 1
