Polygon Construction (Hard)

forthright48 ProgKriya Aug'15
Limits 3s, 512 MB

Meera in going to picnic with her friends. They are going to have lots of fun. They will be doing various activities such as swimming in river, climbing trees, hunting for mushrooms and roasted marshmallows! Before they leave for picnic, they distributed responsibilities among themselves.

Meera is given the responsibility to bring sticks using which everyone will roast their marshmallows. So Meera went to a nearby store, and bought a bundle of sticks with various length.

Meera is really excited about the picnic. It’s already the night before the event, and she is having problem sleeping. So, instead of counting sheep, she thought she would solve a problem that involved the marshmallow sticks.

She bought N sticks of different length. She gave each of them an unique index from 1 to N. Now, she wants to calculate the number ways she can take at least 3 sticks from the bundle and build a simple non­degenerate convex polygon? Two ways will be counted different if the set of stick indices differ.

For example, she bought 4 sticks, {1,2,1,2}\{1,2,1,2\}. There are 3 ways to build a simple non­degenerate convex polygon and they are: {1,2,4}\{1,2,4\}, {2,3,4}\{2,3,4\}, {1,2,3,4}\{1,2,3,4\}, where each number is the index of stick used.

Input

The first line of input will contain single positive integer TT (0<T500 < T ≤ 50) which is number of test case.

For each case, the first line will contain a positive integer NN (1N10001 \le N ≤ 1000). The second line will contain N positive integers, LiL_i (1Li10001 \le L_i ≤ 1000), denoting the length of each stick.

Output

For each case, print a single integer which is the number of ways to form a simple non­degenerate convex polygon with at least 3 sides from the bundle of sticks. The answer may be too large, so print the result modulo 109+710^9+7.

Sample

InputOutput
1 
4 
1 2 1 2
3

Submit

Login to submit.

Statistics

55% Solution Ratio
magurmachEarliest, Aug '15
seyedsszFastest, 95917.3s
seyedsszLightest, 131 kB
seyedsszShortest, 967B
Toph uses cookies. By continuing you agree to our Cookie Policy.