n blocks are put in a line. You have k(1<=k<=15) kinds of dope, the i-th dope is enough to paint c_i (1<=c_i<=5) blocks. You may assume the sum of all the c_i equals to n. Your task is to calculate the number of ways to paint the blocks with these kinds of dope, such that no two adjacent blocks are painted with the same kind of dope.

Input

Ten test cases(given one after another, you have to process all!). For each test case, the first line contains an integer k, the second line contains k integers, c₁, c₂, ...c_k.

Output

Ten lines, each contains an integer, the number of ways modulo 1000000007.

Example

Input:
3
1 2 3
5
2 2 2 2 2
10
1 1 2 2 3 3 4 4 5 5
[and 7 test cases more]
Output:
10
39480
85937576
[and 7 test cases more]