Chefina has an array A consisting of N positive integers.

A permutation subsequence of length M is a subsequence that represents a permutation of length M.
 
Now, Chefina asks Chef to find the count of permutation subsequences in array A.
The count can be very large, so output it modulo 1000000007 (10^{9} + 7).

As a reminder:
A subsequence of an array is obtained by deleting some (possibly zero) elements from the array without changing the order of the remaining elements.
A permutation of length M is an array of length M in which every element from 1 to M occurs exactly once.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains an integer N — the length of array A.
- The next line contains N space-separated integers, the elements of the array A.

------ Output Format ------ 

For each test case, output on a new line, the count of permutation subsequences in array A, modulo 10^{9} + 7.

------ Constraints ------ 

$1 ≤ T ≤ 2\cdot 10^{5}$
$1 ≤ N ≤ 2\cdot 10^{5}$
$1 ≤ A_{i} ≤ 10^{9} $
- Sum of $N$ over all test cases does not exceed $2\cdot 10^{5}$. 

----- Sample Input 1 ------ 
2
5
1 2 3 2 4
6
1 3 5 8 9 8

----- Sample Output 1 ------ 
7
1
----- explanation 1 ------ 
Test case $1$: Chef can get $7$ permutation subsequences:
$[1]$ , $[1, 2]$ , $[1, 2]$ , $[1, 2, 3]$ , $[1, 3, 2]$ , $[1, 2, 3, 4]$ , $[1, 3, 2, 4]$.

Test case $2$: Chef can get $1$ permutation subsequence:
$[1]$

Difficulty: MEDIUM
Tags: Combinatorics

Mathematics

Starter code:

Solutions:
from collections import Counter
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	MOD = 10 ** 9 + 7
	C = Counter(arr)
	ans = 0
	L = []
	for i in C:
		L.append((i, C[i]))
	L.sort()
	p = 1
	prev = 0
	for (i, j) in L:
		if i - 1 == prev:
			p *= j
			ans = (ans + p) % MOD
			prev = i
		else:
			break
	print(ans)


for u in range(int(input())):
	n = int(input())
	k = list(map(int, input().split()))
	d = {}
	for j in range(n):
		if k[j] in d:
			d[k[j]] += 1
		else:
			d[k[j]] = 1
	ans = 0
	q = 1
	k = 1
	while 1:
		if q in d:
			q += 1
		else:
			break
	for jj in range(1, q):
		k *= d[jj]
		ans += k
	print(ans % 1000000007)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split(' ')))
	d = dict()
	for i in l:
		if i in d.keys():
			d[i] += 1
		else:
			d[i] = 1
	n = 1
	x = 0
	sum = 0
	while n >= 0:
		if n in d.keys():
			if n == 1:
				x = d[n]
			else:
				x = x * d[n]
			sum = sum + x
			n += 1
		else:
			break
	print(sum % (10 ** 9 + 7))


from collections import Counter
t = int(input())
for _ in range(t):
	sz = int(input())
	N = [int(x) for x in input().split(' ')]
	MOD = 10 ** 9 + 7
	C = Counter(N)
	ans = 0
	L = []
	for i in C:
		L.append((i, C[i]))
	L.sort()
	p = 1
	prev = 0
	for (i, j) in L:
		if i - 1 == prev:
			p *= j
			ans = (ans + p) % MOD
			prev = i
		else:
			break
	print(ans)


import sys
MOD = 1000000007
for _ in range(int(sys.stdin.readline())):
	n = int(sys.stdin.readline())
	a = list(map(int, sys.stdin.readline().split()))
	freq = {}
	for x in a:
		freq[x] = freq.get(x, 0) + 1
	max_val = max(a)
	ran = min(max_val, n)
	temp1 = freq.get(1, 0)
	som = temp1
	for i in range(2, ran + 1):
		if i not in freq:
			break
		temp1 = temp1 * freq[i] % MOD
		som = (som + temp1) % MOD
	print(som)


for a in range(int(input())):
	x = int(input())
	mod = 10 ** 9 + 7
	l = list(map(int, input().split()))
	g = {}
	for i in l:
		if i not in g:
			g[i] = 0
		g[i] += 1
	j = 1
	ans = 0
	p = 1
	while j in g:
		cur = p % mod * (g[j] % mod) % mod
		p = cur
		ans += cur
		j += 1
	print(ans % mod)


from collections import Counter
t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	d = Counter(l)
	s = 0
	inc = 1
	i = 1
	while i in d:
		inc = inc * d[i]
		s = s + inc
		i += 1
	print(s % 1000000007)


import sys
input = sys.stdin.readline
modulas = 1000000007

def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		array1 = list(map(int, input().split()))
		subseq = {}
		for i in range(n):
			if array1[i] not in subseq:
				subseq[array1[i]] = 1
			else:
				subseq[array1[i]] += 1
		sumation = 0
		lastsumation = 1
		for i in range(1, n + 1):
			multiply = lastsumation * subseq.get(i, 0)
			multiply = multiply % modulas
			sumation += multiply
			lastsumation = multiply
			sumation = sumation % modulas
		print(sumation)
main()


mod = 1000000007
case = int(input())
for _ in range(case):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	arr.sort()
	number = 1
	found = False
	count = 0
	res = 0
	instance = 1
	i = 0
	while i < n:
		if arr[i] == number:
			found = True
			count += 1
		elif not found:
			break
		else:
			instance *= count
			res = (res % mod + instance % mod) % mod
			count = 0
			number += 1
			found = False
			i -= 1
		i += 1
	if found:
		res = (res % mod + instance % mod * count % mod % mod) % mod
	print(res)


import sys
sys.setrecursionlimit(10 ** 7)
mod = 10 ** 9 + 7

def readInt():
	return int(input())

def readIntList():
	return list(map(int, input().split()))

def readStringList():
	return list(input())

def readStringListWithSpace():
	return list(input().split())

def readString():
	return input()
import math

def execute():
	for _ in range(readInt()):
		n = readInt()
		a = readIntList()
		hmap = {}
		for i in a:
			if i in hmap:
				hmap[i] += 1
			else:
				hmap[i] = 1
		b = [[k, v] for (k, v) in hmap.items()]
		b.sort()
		prev = 0
		res = 0
		p = 1
		for (i, j) in b:
			if i - 1 == prev:
				prev = i
				p *= j
				res = (res + p) % mod
			else:
				break
		print(res)
execute()


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	MOD = 10 ** 9 + 7
	freq = {}
	for num in a:
		freq[num] = freq.get(num, 0) + 1
	s = 0
	prevPerm = 1
	flag = True
	for i in range(1, n + 1):
		if i in freq:
			calc = freq[i] * prevPerm
			s += calc
			prevPerm = calc
		else:
			print(s % MOD)
			flag = False
			break
	if flag:
		print(s % MOD)


import random
from collections import Counter
MOD = 10 ** 9 + 7

def gen_list():
	a = []
	for i in range(1, 100):
		a += [i] * random.randint(11, 20)
	print(len(a), Counter(a))
	return a

def solve():
	n = int(input())
	a = Counter(map(int, input().split()))
	tot = 0
	if a[1] == 0:
		print(tot)
		return
	tot = a[1]
	prev = a[1]
	i = 2
	while a[i] > 0:
		prev *= a[i]
		tot += prev
		if tot >= MOD:
			tot = tot % MOD
		i += 1
	print(tot % MOD)
for _ in range(int(input())):
	solve()


t = int(input())
ans = []
mod = 10 ** 9 + 7
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	gg = {}
	for i in a:
		if i not in gg:
			gg[i] = 0
		gg[i] += 1
	x = 1
	ans = 0
	p = 1
	while x in gg:
		curr = p % mod * (gg[x] % mod) % mod
		p = curr
		ans += curr
		x += 1
	print(ans % mod)


for _ in range(int(input())):
	n = int(input())
	dici = {}
	li = list(map(int, input().split()))
	for i in li:
		if i in dici:
			dici[i] += 1
		else:
			dici[i] = 1
	ans = 0
	temp = 1
	for i in range(1, n + 1):
		if i in dici:
			temp *= dici[i]
			ans += temp
		else:
			break
	print(ans % (10 ** 9 + 7))


from statistics import mode
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	dit = {}
	for i in arr:
		if i in dit:
			dit[i] += 1
		else:
			dit[i] = 1
	mod = 1000000007
	ans = 0
	prev = 1
	last = 1
	while last in dit:
		prev *= dit[last]
		ans = (ans + prev) % mod
		last += 1
	print(ans)


from collections import Counter
for k in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	c = Counter(l)
	ans = 0
	l2 = []
	MOD = 10 ** 9 + 7
	for i in c:
		l2.append((i, c[i]))
	p = 1
	l2.sort()
	pr = 0
	for (i, j) in l2:
		if i - 1 == pr:
			p *= j
			ans = (ans + p) % MOD
			pr = i
		else:
			break
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	d = {}
	for i in l:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	s = 0
	p = 1
	i = 1
	while i in d:
		p *= d[i]
		s = s + p
		i += 1
	print(s % 1000000007)


from collections import Counter
t = int(input())

def fun(lst):
	for i in range(1, len(lst) + 4):
		if i not in lst:
			break
	return i - 1
mod = 1000000007
for _ in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	xnum = fun(lst)
	clist = Counter(lst)
	x = clist[1]
	prv = x
	for i in range(2, xnum + 1):
		vl = clist[i]
		prv = vl * prv
		x += prv
	print(x % mod)


from collections import Counter
m = 10 ** 9 + 7
for _ in range(int(input())):
	a = int(input())
	b = list(map(int, input().split()))
	l = Counter(b)
	c = 0
	s = 1
	for i in range(1, a + 1):
		if l[i] == 0:
			break
		temp = s * l[i]
		c += temp
		c = c % m
		s = s * l[i]
	print(c)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	num = 0
	while num + 1 in l:
		num += 1
	frq = {}
	l = sorted(l)
	for i in l:
		if i <= num:
			if i in frq:
				frq[i] += 1
			else:
				frq[i] = 1
	prev = 1
	cnt = 0
	for i in frq:
		prev = prev * frq[i]
		cnt += prev
	print(cnt % 1000000007)


from collections import Counter

def inparr():
	tmparr = [int(i) for i in input().split()]
	return tmparr
for _ in range(int(input())):
	N = int(input())
	rmod = int(1000000000.0) + 7
	arr = Counter(inparr())
	maxa = max(arr)
	prod = 1
	res = 0
	for i in range(1, maxa + 1):
		if arr[i] == 0:
			break
		else:
			prod *= arr[i]
			res += prod
	print(res % rmod)


t = int(input())
while t:
	t -= 1
	n = int(input())
	arr = list(map(int, input().split()))
	freq = {}
	m = 1000000007
	for x in arr:
		if x in freq:
			freq[x] += 1
		else:
			freq[x] = 1
	(x, p, c) = (1, 1, 0)
	while x in freq and freq[x] > 0:
		cur = p * freq[x] % m
		c += cur
		p = cur
		c %= m
		x += 1
	print(c)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	count = [0] * n
	for e in a:
		if e <= n:
			count[e - 1] += 1
	ans = [0] * n
	t = 1
	ans[0] = count[0]
	if ans[0] != 0:
		for i in range(1, len(count)):
			if count[i] != 0:
				ans[i] = ans[i - 1] * count[i] % 1000000007
			else:
				break
	print(sum(ans) % 1000000007)


t = int(input())
for i in range(t):
	n = int(input())
	a = map(int, input().split(' '))
	c = {}
	l = sorted(a)
	j = 1
	while j < len(l):
		if int(l[j]) - int(l[j - 1]) > 1:
			del l[j:]
		else:
			j += 1
	c = {}
	for item in l:
		c[item] = c.get(item, 0) + 1
	p = 1
	d = 0
	if c.get(1, 0) != 0:
		for k in c:
			p *= c[k]
			d += p
	print(d % (10 ** 9 + 7))


from collections import Counter
MOD = 10 ** 9 + 7
for _ in range(int(input())):
	numberOfElements = int(input())
	tempInput = list(map(int, input().split()))
	freq = Counter(tempInput)
	freqList = []
	for i in freq:
		freqList.append((i, freq[i]))
	freqList.sort()
	total = 1
	previousI = 0
	result = 0
	for (i, j) in freqList:
		if i - 1 == previousI:
			total *= j
			previousI = i
			result = (result + total) % MOD
			pass
		else:
			break
	print(result)


mod = int(1000000000.0 + 7)
MOD = 998244353

def add(a, b):
	return (a % mod + b % mod) % mod

def sub(a, b):
	return (a - b + mod) % mod

def mul(a, b):
	return a % mod * (b % mod) % mod

def div(a, b):
	return mul(a, pow(b, mod - 2, mod))
for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	arr.sort()
	ans = 0
	prev = 1
	i = 0
	t = 1
	while i < n:
		j = i
		while j < n and arr[j] == t:
			j += 1
		if i == j:
			break
		val = mul(j - i, prev)
		ans = add(ans, val)
		prev = val
		i = j
		t += 1
	print(ans)


MOD = int(1000000000.0) + 7
t = int(input())
for _ in range(t):
	n = int(input())
	mp = {}
	x = list(map(int, input().split()))
	for i in x:
		mp[i] = mp.get(i, 0) + 1
	ans = 0
	prev = 1
	for i in range(1, n + 1):
		temp = prev * mp.get(i, 0)
		temp %= MOD
		ans += temp
		prev = temp
		ans %= MOD
	print(ans)


for i in range(int(input())):
	M = 1000000007
	n = int(input())
	lst = [int(x) for x in input().split()]
	d = {}
	for j in lst:
		if j not in d.keys():
			d[j] = 1
		else:
			d[j] += 1
	ct = 1
	ans = 0
	mul = 1
	for j in sorted(d.keys()):
		if j == ct:
			mul *= d[j]
			ans += mul
		else:
			break
		ct += 1
	print(ans % M)


import sys
sys.setrecursionlimit(10 ** 6)

def get_count(arr, i):
	if i == 0:
		freq = dict()
		if arr[0] == 1:
			freq[1] = 1
			return (freq, True)
		return (freq, False)
	(freq, isokay) = get_count(arr, i - 1)
	if isokay is True:
		flag = False
		if arr[i] == 1:
			flag = True
			freq[1] = freq.get(1, 0) + 1
		elif freq.get(arr[i] - 1, -1) != -1:
			flag = True
			freq[arr[i]] = freq.get(arr[i], 0) + freq[arr[i] - 1]
		return (freq, flag)
	return (freq, False)
t = int(input())
for z in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	arr.sort()
	(freq_map, isokay) = get_count(arr, n - 1)
	ans = 0
	for key in freq_map:
		ans += freq_map[key]
	print(ans % (10 ** 9 + 7))


ans = []
nq = int(input())
for _ in range(nq):
	n = int(input())
	a = list(map(int, input().split()))
	d = {}
	for ai in a:
		if ai in d:
			d[ai] += 1
		else:
			d[ai] = 1
	i = 1
	count = 0
	while i in d:
		if i == 1:
			curr = d[i]
			count = d[i]
		else:
			curr = curr * d[i]
			count += curr
		i += 1
	val = count % 1000000007
	ans.append(val)
print(*ans, sep='\n')


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	C = Counter(l)
	a = []
	for i in C:
		a.append((i, C[i]))
	a.sort()
	m = int(1000000000.0 + 7)
	p = 1
	ans = 0
	prev = 0
	for (i, j) in a:
		if i - 1 == prev:
			p = p * j
			ans = (ans + p) % m
			prev = i
		else:
			break
	print(ans)


from collections import Counter
T = int(input())
for tc in range(T):
	n = int(input())
	l = list(map(int, input().split(' ')))
	e = 1
	count = 0
	inc = 1
	m = 1000000007
	l.sort()
	d = dict(Counter(l))
	l = list(set(l))
	for (i, j) in enumerate(l):
		inc = d[j] * inc
		if j == e:
			count += inc
			e += 1
		else:
			break
	print(count % m)


from collections import defaultdict
for t in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	dic = defaultdict(int)
	for i in arr:
		dic[i] += 1
	mod = pow(10, 9) + 7
	if 1 not in dic:
		print(0)
		continue
	ans = dic[1]
	tot_prev = ans
	for i in range(2, n + 1):
		new = tot_prev * dic[i]
		ans += new % mod
		tot_prev = new
	print(ans % mod)


from collections import Counter
t = int(input())
for i in range(t):
	N = int(input())
	A = list(map(int, input().split()))
	A.sort()
	count = 1
	j = 1
	while j < N:
		if A[j] == A[j - 1] or A[j - 1] == A[j] - 1:
			count += 1
			j += 1
		else:
			break
	B = A[0:count]
	if B[0] != 1:
		print(0)
	else:
		total = 0
		counter = 1
		for j in Counter(B).values():
			counter = counter * j
			total = total + counter
		total = total % 1000000007
		print(total)


from collections import defaultdict
m1 = int(1000000000.0 + 7)
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = defaultdict(int)
	for i in l:
		d[i] += 1
	m = max(l) + 1
	q = 1
	r = 0
	for i in range(1, m):
		if i in d:
			q *= d[i]
			r += q
		else:
			break
	print(r % m1)


t = int(input())
m = 10 ** 9 + 7
while t:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	d = {}
	l = max(a)
	for i in a:
		d[i] = d.get(i, 0) + 1
	p = 1
	ans = 0
	for i in range(1, l + 1):
		if d.get(i, 0):
			p *= d[i]
			ans += p
		else:
			break
		ans %= m
	print(ans)


for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	d = {}
	for i in arr:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	t = 1
	M = int(1000000000.0 + 7)
	ans = 0
	prod = 1
	while t in d:
		prod = prod * d[t]
		ans = (ans + prod) % M
		t += 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	dic = {}
	a = 0
	for i in range(1, n + 1):
		if i in l:
			a += 1
		else:
			break
	for i in range(1, a + 1):
		dic[i] = 0
	for i in l:
		if i in dic and i <= a:
			dic[i] += 1
	s = 0
	k = 1
	for i in dic:
		s = s + k * dic[i]
		k = k * dic[i]
	print(s % 1000000007)


mod = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	freq = [0] * (n + 1)
	for x in map(int, input().split()):
		if x <= n:
			freq[x] += 1
	(cur, ans) = (1, 0)
	for i in range(1, n + 1):
		cur = cur * freq[i] % mod
		ans += cur
	print(ans % mod)


from collections import Counter
for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	modVal = 10 ** 9 + 7
	freq = Counter(arr)
	tuples = []
	for i in freq:
		tuples.append((i, freq[i]))
	tuples.sort()
	ans = 0
	p = 1
	prev = 0
	for (i, j) in tuples:
		if i - 1 == prev:
			p *= j
			ans = (ans + p) % modVal
			prev = i
		else:
			break
	print(ans)


t = int(input())
hnr = []
for vvc in range(0, t):
	r = int(input())
	fcx = str(input())
	opt = fcx.split(' ')
	xwq = []
	for tt in opt:
		xwq.append(int(tt))
	hnr.append(xwq)
for uu in hnr:
	hk = {}
	for bbv in uu:
		if bbv in hk:
			hk[bbv] += 1
		else:
			hk[bbv] = 1
	abd = len(uu)
	sumd = 0
	pr = 1
	for ingf in range(1, abd + 1):
		try:
			andf = hk[ingf]
			pr *= andf
			sumd += pr
		except:
			break
	print(sumd % (10 ** 9 + 7))


for test_cases in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	m = 1000000007
	d = {}
	for i in l:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	x = 1
	c = 0
	p = 1
	while x in d and d[x] > 0:
		cur = p % m * (d[x] % m) % m
		c += cur
		p = cur
		c = c % m
		x += 1
	print(c)


from collections import Counter
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	q = Counter(l)
	m = 1
	t = 0
	for i in range(1, len(q) + 1):
		if q[i] == 0:
			break
		else:
			t = t + q[i] * m
			m = max(m, q[i] * m)
	print(t % 1000000007)


N = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	cnt = [0] * (n + 1)
	for __ in map(int, input().split()):
		if __ <= n:
			cnt[__] += 1
	curr = 1
	ans = 0
	for i in range(1, n + 1):
		curr = curr * cnt[i] % N
		ans = (ans + curr) % N
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	prev = 1
	mod = 10 ** 9 + 7
	ans = 0
	d = {}
	for i in a:
		d[i] = 1 + d.get(i, 0)
	for i in range(1, 10 ** 9):
		if i not in d:
			break
		else:
			temp = prev * d[i]
			temp = temp % mod
			ans += temp
			prev = temp
			ans = ans % mod
	print(ans)


mod = 10 ** 9 + 7
for _ in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	count = {}
	prod = 1
	res = 0
	for i in range(N):
		if count.get(arr[i], 0):
			count[arr[i]] += 1
		else:
			count[arr[i]] = 1
	for i in range(1, N + 1):
		if count.get(i, 0):
			prod *= count[i]
			res += prod
		else:
			prod = 0
	print(res % mod)


from collections import Counter
M = 10 ** 9 + 7
test = int(input())
for _ in range(test):
	n = int(input())
	ls = list(map(int, input().split(' ')))
	C = Counter(ls)
	subseq = 0
	if C[1] == 0:
		print(0)
		continue
	else:
		subseq = C[1]
	temp = subseq
	for i in range(2, n + 1):
		if C[i] == 0:
			break
		else:
			subseq += C[i] * temp
			temp = C[i] * temp
	print(subseq % M)


from collections import Counter
MOD = 10 ** 9 + 7
for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	d = Counter(A)
	res = 0
	i = 1
	tmp = 1
	while d[i] != 0:
		tmp *= d[i]
		res += tmp % MOD
		i += 1
	print(res % MOD)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = {}
	mod = 1000000007
	for i in a:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	d = [[i, d[i]] for i in d]
	d.sort()
	d = [[0, 1]] + d
	ans = 0
	for i in range(1, len(d)):
		if d[i][0] != i:
			print(ans)
			break
		d[i][1] = d[i][1] * d[i - 1][1]
		ans = (ans + d[i][1]) % mod
	else:
		print(ans)


from collections import Counter as cc
for t in range(int(input())):
	m = 1000000007
	n = int(input())
	a = list(map(int, input().split()))
	b = cc(a)
	c = []
	for i in b:
		c.append([i, b[i]])
	c.sort()
	p = 1
	s = 0
	k = 1
	for i in c:
		if i[0] != p:
			break
		k *= i[1]
		s = (s + k) % m
		p += 1
	print(s)


MOD = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	d = {}
	for i in range(0, n):
		if x[i] in d:
			d[x[i]] += 1
		else:
			d[x[i]] = 1
	v = n
	for i in range(1, n + 1):
		if i not in d:
			v = i - 1
			break
	if v == 0:
		print('0')
	else:
		prev = d[1]
		ans = d[1]
		for i in range(2, v + 1):
			t = prev * d[i]
			ans = (ans + t) % MOD
			prev = t
		ans %= MOD
		print(ans)


a = int(input())
for i in range(a):
	n = int(input())
	a = list(map(int, input().split()))
	d = {}
	for j in a:
		if d.get(j) is None:
			d[j] = 1
		else:
			d[j] += 1
	ans = 0
	temp = 1
	for j in range(1, n + 1):
		if d.get(j) is None:
			break
		else:
			count = 1
			temp = temp * d[j]
			ans = ans + temp
	print(ans % 1000000007)


mod = 10 ** 9 + 7

def solve(arr, n):
	m = {}
	for i in arr:
		if i not in m.keys():
			m[i] = 0
		m[i] += 1
	ans = [0] * (n + 1)
	if 1 not in m.keys():
		print(0)
		return
	ans[1] = m[1]
	for i in range(2, n + 1):
		if i not in m.keys():
			break
		ans[i] += ans[i - 1] * m[i]
		ans[i] %= mod
	res = 0
	for i in ans:
		res += i
		res %= mod
	print(res)
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	solve(arr, n)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	k = []
	if l[0] == 1:
		k = {1: 1}
		i = 0
		while l[i] == l[i + 1] or l[i + 1] == l[i] + 1:
			if l[i + 1] in k:
				k[l[i]] += 1
			else:
				k[l[i + 1]] = 1
			i += 1
			if i >= n - 1:
				break
		ans = 1
		sum = 0
		h = 10 ** 9 + 7
		for i in k:
			ans = ans * k[i] % h
			sum = sum % h + ans % h
		print(sum % h)
	else:
		print(0)


from collections import Counter
t = int(input())
for i in range(t):
	n = int(input())
	p = [int(ele) for ele in input().split()][:n]
	p.sort()
	d = Counter(p)
	if n == 1 and p[0] == 1:
		print(1)
		continue
	l = list(set(p))
	c = 1
	for i in range(len(l)):
		if l[i] != c:
			break
		c += 1
	s = 0
	k = 1
	for i in range(1, c):
		k *= d[i]
		s = (s + k) % 1000000007
	print(s)


mod = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	freq = [0] * (n + 1)
	v = list(map(int, input().split()))
	for x in v:
		if x <= n:
			freq[x] += 1
	(cur, res) = (1, 0)
	for i in range(1, n + 1):
		cur = cur * freq[i] % mod
		res = (res + cur) % mod
	print(res)


from collections import Counter
T = int(input())
for i in range(T):
	N = int(input())
	arr = list(map(int, input().split()))
	C = Counter(arr)
	listy = []
	for i in range(1, len(C) + 1):
		if i + 1 not in C:
			listy.append(C[i])
			break
		else:
			listy.append(C[i])
	MOD = 10 ** 9 + 7
	multiple = 1
	count = 0
	for i in listy:
		multiple *= i
		count = (count + multiple) % MOD
	print(count)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = {}
	s = 0
	M = 10 ** 9 + 7
	for j in range(n):
		if l[j] in d:
			d[l[j]] = d[l[j]] + 1
		else:
			d[l[j]] = 1
	b = []
	for j in d:
		b.append((j, d[j]))
	b.sort()
	prev = 0
	m = 1
	for (c, d) in b:
		if c - 1 == prev:
			m = m * d
			s = (s + m) % M
			prev = c
		else:
			break
	print(s)


from collections import Counter

def solve(n):
	a = list(map(int, input().split()))
	fr = []
	c = Counter(a)
	for i in c:
		fr.append((i, c[i]))
	fr.sort()
	mod = 10 ** 9 + 7
	ans = 0
	mult = 1
	prev = 0
	for (i, j) in fr:
		if i - 1 == prev:
			prev = i
			mult *= j
			ans = (ans + mult) % mod
		else:
			break
	print(ans)
for _ in range(int(input())):
	n = int(input())
	solve(n)


def solve(n):
	a = list(map(int, input().split()))
	fr = [0 for i in range(max(a) + 1)]
	for i in a:
		if fr[i] == 0:
			fr[i] = 1
		else:
			fr[i] += 1
	ans = 0
	mult = 1
	for i in range(1, len(fr)):
		if fr[i] == 0:
			print(ans)
			return
		mult *= fr[i]
		ans = (ans + mult) % (10 ** 9 + 7)
	print(ans)
for _ in range(int(input())):
	n = int(input())
	solve(n)


from collections import Counter
for z in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	ans = 0
	ct = 1
	mp = Counter(l)
	for i in range(1, 10 ** 9):
		if i not in mp:
			break
		else:
			ct *= mp[i]
			ans += ct
	print(ans % 1000000007)


from collections import OrderedDict
t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	mod = 1000000007
	h = {}
	for i in a:
		if i not in h:
			h[i] = 1
		else:
			h[i] += 1
	h = OrderedDict(sorted(h.items()))
	prev = 0
	p = 1
	ans = 0
	for i in h:
		if i - 1 == prev:
			p *= h[i]
			ans += p % mod
			prev = i
		else:
			break
	print(ans % mod)
	t -= 1