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<=6) 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

Input consists of multiple test cases, the number of them (<=2000) is given in the very first line. For each test case, the first line contains an integer k, the second line contains k integers, c₁, c₂, ...c_k.

Output

For each test case, output one line with an integer, the number of ways modulo 1000000007.

Example

Input:
3
3
1 2 3
5
2 2 2 2 2
10
1 1 2 2 3 3 4 4 5 5

Output:
10
39480
85937576