Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Polygon Construction (Hard)

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}. 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 (T ≤ 50) which is number of test case.

For each case, the first line will contain a positive integer N (N ≤ 1000). The second line will contain N positive integers, Li (Li ≤ 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+7.

Samples

InputOutput
1 
4 
1 2 1 2
3

Author
  • forthright48's Avatar

    forthright48

    Samiul is a student at North South University and a part-time Software Engineer at Mukto Software Ltd. Sport programming is one of his hobbies. He loves reading manga - One Piece being his favorite.
Discussion
Submit

Login to submit