As you know America’s Presidential Elections are about to take place and the most popular leader of the Republican party Donald Trump is famous for throwing allegations against anyone he meets.

He goes to a rally and meets n people which he wants to offend. For each person i he can choose an integer between 1 to max[i].

He wants to decide in how many ways he can offend all these persons (N) given the condition that all numbers chosen by him for each person are distinct.
So he needs your help to find out the number of ways in which he can do that. If no solution is possible print 0

-----Input-----
The first line of the input contains an integer T (1<=T<=100) denoting the number of test cases. The description of T test cases follows.

The first line of each test case contains a single integer N denoting the number of people Trump wants to offend. The second line contains N space-separated integers maxnumber[0], maxnumber[1], ..., maxnumber[n-1] denoting the maxnumber that trump can choose for each person. 

-----Output-----
For each test case, output a single line containing the number of ways Trump can assign numbers to the people, modulo 1,000,000,007. If it's impossible to assign distinct integers to the people, print 0

-----Constraints-----
- 1 ≤ T ≤ 100
- 1 ≤ N ≤ 50
- 1 ≤ Maxnumber[i] ≤ 3000

-----Example-----
Input:
3
1
4
2
10 5
4
2 3 1 3

Output:
4
45
0


-----Explanation-----
In case 1, He can choose any number from 1 to 4

In case 2,Out of the total 50 combination he can not take (1,1) ,(2,2) , (3,3) ,(4,4) or (5,5).

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 't = eval(input())\n\nfor i in range(t):\n n=eval(input())\n a = list(map(int, input().split()))\n a.sort()\n \n cnt=1\n for ind,x in enumerate(a):\n  cnt*=(x-ind) \n  if x-ind<=0:\n   cnt=0\n   break\n print(cnt%(10**9+7)) \n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 17702