Candy Game

Albert, a math teacher, invented a game for the children in his class who love candy. The children are still young and know only the natural numbers, and each child knows a different range of natural numbers. For convenience, assume the children are numbered 1 through n, and the i-th child knows the natural numbers from 1 to x[i].

The game proceeds by the following rules.

1. At the start of each turn, the children each choose any natural number they know and write it on a piece of paper.
2. Once everyone has written a number, Albert collects the n pieces of paper.
3. Albert sorts these numbers in nondecreasing order to form a sequence of length n (call it sequence A).
4. If sequence A has ever been formed in a previous turn, the sequence is discarded and the game continues.
5. If sequence A has never been formed before, Albert gives each child one candy and the game continues.
6. The game ends completely once every possible (sorted) sequence has been formed.

Since every child knows only some of the natural numbers, the game ends at some point. Albert has to prepare the candy in advance, so he wants to know the largest number of candies he may have to give out. Given the number of students n and the range of natural numbers each student knows, find the largest number of candies Albert has to give out and help him. This number can be very large, so compute it modulo 1,000,000,007.

For example, suppose Albert's class has two children and both know only the natural numbers from 1 to 3. In this case there are six sequences sorted in nondecreasing order: {1, 1}, {1, 2}, {1, 3}, {2, 2}, {2, 3}, {3, 3}. On the turn each sequence is formed for the first time, Albert has to give out two candies, so he must prepare 12 candies in advance.

The first line gives the number of test cases T (1 <= T <= 10).

Each test case is given over two lines. The first line gives the number of students n (1 <= n <= 200), and the second line gives n natural numbers separated by spaces that represent the array x[]. For each i, 1 <= x[i] <= 200 holds.

For each test case, print the largest number of candies Albert must prepare, modulo 1,000,000,007.

• Case 1: One child knows the numbers from 1 to 3, so the answer is 3. There are three sorted sequences: {1}, {2}, and {3}.
• Case 2: This case is used as the example in the problem.
• Case 3: In this case there are five sorted sequences: {1, 1, 1}, {1, 1, 2}, {1, 1, 3}, {1, 2, 2}, {1, 2, 3}. Since there are three students, Albert gives out 3 candies on the turn each sequence is formed for the first time, so he must prepare 15 candies in total.
• Case 4: Note that the answer can become very large, so it must be printed modulo 1,000,000,007. In this case there are 1,604,563,870 sorted sequences, and since there are six children, 9,627,383,220 candies are needed in total. The remainder of 9,627,383,220 divided by 1,000,000,007 is 627,383,157.