Tianjin University Online Judge
Contests Virtual Contests Problems Submit Runs Status Rank List Forum

3489.   Dog Numbering
Time Limit: 2.0 Seconds   Memory Limit: 65536K
Total Runs: 2476   Accepted Runs: 744



Miss Kim has dogs, and she wants to assign a distinct integer to each dog so she can easily identify them. The dogs have expressed their preferences to Miss Kim. The i-th dog wants an integer between 1 and maxNumber[i], inclusive. Miss Kim must obey the preferences of all their dogs.

Input

The first line will contain the number of test cases. Each case has two lines of input. The first line will contain a integer N (1 ≤ N ≤ 50) indicating the number of dogs. The second line will contain N integers corresponding to maxNumber[i](1 ≤ maxNumber[i] ≤ 1000), separated by spaces.

Output

For each case output a integer in a line, that is the number of ways she can assign numbers to her dogs, modulo 1,000,000,007. If it's impossible to assign distinct integers to the dogs, output 0.

Sample Input

4
1
5
4
4 4 4 4
2
5 8
3
2 1 2

Sample Output

5
24
35
0



Source: TJU Team Selection Contest 2010 (2)
Submit   List    Runs   Forum   Statistics

Tianjin University Online Judge v1.3.0
Maintance:G.D.Retop. Developer: SuperHacker, G.D.Retop