## NGON - Many polygons

There is a regular n-gon. We mark some points on its sides: a1 points on the first side, a2 on the second ... an on the last. Marked points do not coincide with the vertices n-gon. The question is, how many different convex nondegenerate (n-1)-gons you can build, using marked points as vertices?

### Input

The first line of input contains the number t - the number of tests. Next comes the description of t tests. Each test consists of two lines. The first line of the test contains an integer n - number of vertices of original n-gon. Second line of the test lists n integers a1, a2, ..., an - number of points marked on each side.

1 <= t <= 20
4 <= n <= 1000
1 <= ai <= 100

### Output

For each test, print out the answer to the problem modulo 1000000007.

### Example

```Input:
3
4
2 2 2 2
5
2 2 2 2 2
5
10 20 30 40 50

Output:
56
210
16207125

```

 Added by: Spooky Date: 2010-03-12 Time limit: 0.258s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All except: NODEJS OBJC PERL6 SQLITE VB.NET Resource: Advancement Spring 2010, http://sevolymp.uuuq.com/