Polygon Construction (Hard)

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\}$. There are 3 ways to build a simple non­degenerate convex polygon and they are: $\{1,2,4\}$, $\{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 $T$ ($0 < T ≤ 50$) which is number of test case.

For each case, the first line will contain a positive integer $N$ ($1 \le N ≤ 1000$). The second line will contain N positive integers, $L_i$ ($1 \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 $10^9+7$.

Sample

Input	Output
1 4 1 2 1 2	3