Oz and nakul have N robots, and they want to assign a distinct integer to each robot so that they can easily identify them. Also robots have already expressed their preferences to Oz and nakul. The \(k-th\) robot wants an integer between 1 and \(MAX[k]\), inclusive. Oz and nakul must obey the preferences of all their robots.
Now you are given the list \(MAX[]\), you have to output the number of ways they can assign numbers to their robots, modulo \(10\)⁹7. If it's impossible to assign distinct integers to the robots, output 0.

Input:
First line of the input contains a single integer T denoting the number of test cases.
First line of each test case consists of an integer - N.
Second line of each test case consists of N space separated integers of list \(MAX[]\).

Output:
For each test case, output the required answer in a separate line.

Constraints:

• 1 ≤ T ≤ 10
• 1 ≤ N ≤ 1000
• 1 ≤ \(MAX[k]\) ≤ 1000 for k=1,2..N