Submit  All submissions  Best solutions  Back to list 
NGON  Many polygons 
There is a regular ngon. 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 ngon. The question is, how many different convex nondegenerate (n1)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 ngon. 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:  20100312 
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
20210423 20:05:02 David
Solved in Java!. After this problem, solve https://www.spoj.com/problems/SWARM/ 

20171116 19:28:38
too strict time limit for java 

20140921 13:09:34 narek
Any more test cases? 

20140712 14:27:14 Naman Goyal
mistake in modulo operation costed me so many WA's. Finally AC in 0.78sec. Last edit: 20140712 16:27:50 

20140614 12:34:04 farhad chowdhury
Getting TLE 

20130325 09:46:47 Divanshu
Optimisations required to AC. Too strict time limit! 

20120928 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: 20120929 00:04:48 

20120204 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 