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.

Constraints

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:1s
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/

hide comments
2021-04-23 20:05:02 David
Solved in Java!. After this problem, solve https://www.spoj.com/problems/SWARM/
2017-11-16 19:28:38
too strict time limit for java
2014-09-21 13:09:34 narek
Any more test cases?
2014-07-12 14:27:14 Naman Goyal
mistake in modulo operation costed me so many WA's. Finally AC in 0.78sec.

Last edit: 2014-07-12 16:27:50
2014-06-14 12:34:04 farhad chowdhury
Getting TLE
2013-03-25 09:46:47 Divanshu
Optimisations required to AC. Too strict time limit!
2012-09-28 22:08:17 Alex Anderson
=|, Java is too slow, cause I am pretty confident in my last submission.

EDIT: Although this has happened in another problem too, so maybe there is yet another magnitude of optimization to do.

EDIT2: Finally got it, had to convert to C++ and do more minor optimizations.

Last edit: 2012-09-29 00:04:48
2012-02-04 13:36:55 Allada Revanth Kumar
could not understand, why i am getting wrong ans... all the test cases are working, fine please help me
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.