There are N cards on the table and each has a number between 0 and N. Let us denote the number on the i^{th} card by c_{i}. You want to pick up all the cards. The i^{th} card can be picked up only if at least c_{i} cards have been picked up before it. (As an example, if a card has a value of 3 on it, you can't pick that card up unless you've already picked up 3 cards previously) In how many ways can all the cards be picked up?

Input Format 

The first line contains the number of test cases T. T test cases follow. Each case contains an integer N on the first line, followed by integers c_{1},..c_{i},...,c_{N} on the second line.

Output Format 

Output T lines one corresponding to each test case containing the required answer for the corresponding test case. As the answers can be very big, output them modulo 1000000007.

Constraints: 

1 <= T <= 10 

1 <= N <= 50000 

0 <= c_{i} <= N

Sample Input:  

3  
3  
0 0 0  
3  
0 0 1  
3  
0 3 3

Sample Output:  

6  
4  
0

Sample Explanations:

For the first case, the cards can be picked in any order, so there are 3! = 6 ways. 

For the second case, the cards can be picked in 4 ways: {1,2,3}, {2,1,3}, {1,3,2}, {2,3,1}.  

For the third case, no cards can be picked up after the first one, so there are 0 ways to pick up all cards.

Source: hackerrank | Difficulty: EASY
Tags: Combinatorics


Solutions:
cs = int(input())
for c in range(cs):
	l = int(input())
	num = [int(i) for i in input().strip().split()]
	num.sort()
	rt = 1
	for i in range(l):
		if i < num[i]:
			rt = 0
			break
		else:
			rt *= i + 1 - num[i]
			rt %= 10 ** 9 + 7
	print(rt)


import collections, sys
T = int(sys.stdin.readline())
for i in range(T):
	N = int(sys.stdin.readline())
	c = list(map(int, sys.stdin.readline().strip().split(' ')))
	count = collections.Counter(c)
	n = 0
	combinations = 1
	possible_terms = 0
	while True:
		if n in count:
			possible_terms += count[n]
		if possible_terms > 0:
			combinations *= possible_terms
			combinations %= 1000000007
			possible_terms -= 1
			n += 1
		else:
			break
	print(0 if n < max(c) else combinations)


import sys

def main(f=sys.stdin):
	rounds = int(f.readline())
	for r in range(rounds):
		junk = f.readline()
		array = sorted((int(i) for i in f.readline().split()))
		ways = 1
		picked = 0
		pool = 0
		i = 0
		while i < len(array):
			c = array[i]
			if c <= picked:
				pool += 1
				i += 1
				continue
			elif pool == 0:
				ways = 0
				break
			else:
				ways *= pool
				ways %= 1000000007
				pool -= 1
				picked += 1
		while pool > 1:
			ways *= pool
			ways %= 1000000007
			pool -= 1
		print(ways)
main()


rem = 1000000007
T = int(input())
for i in range(T):
	n = int(input())
	vals = [int(j) for j in input().split()]
	counts = {}
	for j in vals:
		if j in counts:
			counts[j] += 1
		else:
			counts[j] = 1
	prod = 1
	curr = 0
	for j in range(n):
		if j in counts:
			curr += counts[j]
		if j > 0:
			curr -= 1
		if curr <= 0:
			prod = 0
			break
		prod *= curr
		prod %= rem
	print(prod)


from collections import Counter
import sys
stream = sys.stdin
T = int(stream.readline())
for _ in range(T):
	N = int(stream.readline())
	a = list(map(int, stream.readline().strip().split()))
	ways = 1
	ad = Counter(a)
	curr = 0
	for v in range(1, N + 1):
		curr += ad.get(v - 1, 0)
		ways *= curr - v + 1
	print(ways % 1000000007)


def solution(c, modulo=1000000007):
	c = sorted(c)
	n = len(c)
	d = []
	(j, ni) = (0, 0)
	for i in range(n):
		while j < n and c[j] <= i:
			j += 1
			ni += 1
		d.append(ni)
	result = 1
	for i in range(n):
		dn = d[i] - i
		if dn > 0:
			result *= dn
			result %= modulo
		else:
			return 0
	return result
t = int(input())
for i in range(t):
	n = int(input())
	c = [int(ci) for ci in input().split()]
	print(solution(c))


def solve(c):
	c.sort()
	N = len(c)
	i = 0
	answer = 1
	for n in range(N):
		while i < N and c[i] <= n:
			i += 1
		answer *= i - n
		answer %= 1000000007
	return answer
from sys import stdin
T = int(stdin.readline())
for _ in range(T):
	N = int(stdin.readline())
	c = list(map(int, stdin.readline().split()))
	print(solve(c))


def ways(k, v):
	f = {}
	for i in v:
		if i not in f:
			f[i] = 1
		else:
			f[i] += 1
	s = 0
	modulo = 1000000007
	ret = 1
	for i in range(k):
		if i in f:
			s += f[i]
		ret *= (s - i) % modulo
	return ret % modulo
t = int(input())
for i in range(t):
	k = int(input())
	v = [int(j) for j in input().split()]
	print(ways(k, v))


numtests = int(input())
tests = []
for i in range(numtests):
	input()
	tests.append(input().split())
for test in tests:
	z = sorted([int(x) for x in test])
	ans = 1
	for i in range(len(z)):
		if int(z[i]) > i:
			ans = 0
			break
		else:
			ans = ans * (i - int(z[i]) + 1)
	print(ans % 1000000007)


T = int(input())
for _ in range(T):
	n = int(input())
	cs = sorted([int(c) for c in str(input()).split()])
	ret = 1
	if n <= cs[n - 1] or cs[0] != 0:
		ret = 0
	else:
		for (j, cj) in reversed(list(enumerate(cs))):
			if j < cj:
				ret = 0
				break
			else:
				ret = ret * (j - cj + 1) % 1000000007
	print(ret)


import collections, sys
T = int(sys.stdin.readline())
for i in range(T):
	N = int(sys.stdin.readline())
	c = list(map(int, sys.stdin.readline().split()))
	count = collections.Counter(c)
	n = 0
	combinations = 1
	possible_terms = 0
	while True:
		if n in count:
			possible_terms += count[n]
		if possible_terms > 0:
			combinations *= possible_terms
			combinations %= 1000000007
			possible_terms -= 1
			n += 1
		else:
			break
	print(0 if n < max(c) else combinations)


from collections import Counter
t = int(input())
for counter in range(t):
	n = int(input())
	cards = Counter([int(x) for x in input().split()])
	numWays = 1
	totalCards = 0
	for i in range(n):
		totalCards += cards[i]
		numWays *= totalCards - i
		numWays %= 1000000007
		if numWays <= 0:
			numWays = 0
			break
	print(numWays)


N = 50000
modc = 1000000007
t = int(input())
for _ in range(t):
	n = int(input())
	c = list(map(int, input().split()))
	cc = [0] * (n + 1)
	for ci in c:
		cc[ci] += 1
	(possible, total) = (0, 1)
	for k in range(n):
		possible += cc[k]
		if possible == 0:
			total = 0
			break
		total = total * possible % modc
		possible -= 1
	print(total)


t = int(input())
for dsfsfj in range(t):
	n = int(input())
	tab = list(map(int, input().split()))
	tab.sort()
	result = 1
	current = 0
	picked = 0
	for i in range(n):
		for j in range(i + current, n):
			if tab[j] > picked:
				break
			current += 1
		if current == 0:
			result = 0
			break
		result = result * current % 1000000007
		picked += 1
		current -= 1
	print(result)


T = int(input())
for _ in range(T):
	N = int(input())
	cards = [0] * (N + 1)
	for i in [int(x) for x in input().split()]:
		cards[i] += 1
	if cards[-1] or not cards[0]:
		print(0)
		continue
	N = cards.pop(-1)
	c = 1
	ways = 1
	for i in cards:
		c += i
		c -= 1
		ways *= c
		ways %= 1000000007
	print(ways)


import math, functools, operator

def getCardChoices(cards):
	hand = 0
	stock = 0
	choices = 1
	for n in cards:
		if n <= hand:
			stock += 1
		else:
			if n > stock + hand:
				return 0
			numCardsFromStock = n - hand
			choices *= functools.reduce(operator.mul, range(stock, stock - numCardsFromStock, -1))
			stock -= numCardsFromStock - 1
			hand += numCardsFromStock
	return math.factorial(stock) * choices % 1000000007
for t in range(int(input())):
	numInts = int(input())
	arr = [int(i) for i in input().split()]
	arr.sort()
	print(getCardChoices(arr))


import collections, sys
t = int(input())
for _ in range(t):
	N = int(input())
	c = list(map(int, sys.stdin.readline().split()))
	count = collections.Counter(c)
	n = 0
	combinations = 1
	possible_terms = 0
	while True:
		if n in count:
			possible_terms += count[n]
		if possible_terms > 0:
			combinations *= possible_terms
			combinations %= 1000000007
			possible_terms -= 1
			n += 1
		else:
			break
	print(0 if n < max(c) else combinations)


p = int(1000000000.0) + 7
t = int(input())
for tst in range(t):
	n = int(input())
	l = list(map(int, input().strip().split()))
	l.sort()
	ind = 0
	ans = 1
	curr = 0
	tmp = 0
	ser = l[0]
	last = 0
	for i in range(n):
		if l[i] > curr:
			ind = 1
			break
		else:
			curr += 1
			if l[i] == ser:
				tmp += 1
			else:
				ser = l[i]
				for j in range(last, l[i]):
					ans = ans * tmp % p
					tmp -= 1
				tmp += 1
				last = l[i]
	if ind == 1:
		print(0)
	else:
		for j in range(last, n):
			ans = ans * tmp % p
			tmp -= 1
		print(ans)


modulo = 10 ** 9 + 7
for case in range(int(input())):
	n = int(input())
	c = [int(item) for item in input().strip().split()]
	s = [0] * (n + 1)
	count = 0
	for i in c:
		s[i] += 1
	rem = 0
	if s[n] > 0:
		print(0)
	else:
		answer = 1
		for i in range(n):
			rem += s[i]
			answer *= rem
			answer %= modulo
			rem -= 1
		print(answer)


import collections, sys
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	c = list(map(int, sys.stdin.readline().split()))
	count = collections.Counter(c)
	n = 0
	combinations = 1
	possible_terms = 0
	while True:
		if n in count:
			possible_terms += count[n]
		if possible_terms > 0:
			combinations *= possible_terms
			combinations %= 1000000007
			possible_terms -= 1
			n += 1
		else:
			break
	print(0 if n < max(c) else combinations)


for _ in range(int(input())):
	n = int(input())
	numbers = [int(x) for x in input().strip().split()]
	count = [0 for _ in range(n + 1)]
	for number in numbers:
		count[number] += 1
	for i in range(1, n + 1):
		count[i] += count[i - 1]
	result = 1
	mod = 10 ** 9 + 7
	for i in range(n):
		result *= count[i] - i
		result %= mod
	print(result)


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

def main():
	ncases = int(input())
	for _ in range(ncases):
		ncards = int(input())
		card = [int(fld) for fld in input().split()]
		assert ncards == len(card)
		print(countpicks(card))

def countpicks(card):
	ans = 1
	count = Counter(card)
	avail = 0
	for pick in range(len(card)):
		avail += count[pick]
		ans = ans * avail % MOD
		avail -= 1
	return ans
main()


t = int(input())
for _ in range(t):
	choices = list(range(int(input()), 0, -1))
	bad = [0] * (len(choices) + 1)
	for card in [int(x) for x in input().split()]:
		bad[card] += 1
	for i in range(len(bad) - 2, -1, -1):
		bad[i] += bad[i + 1]
	bad = bad[1:]
	choices = [max(c - b, 0) for (c, b) in zip(choices, bad)]
	ans = 1
	for c in choices:
		ans *= c
		ans %= 1000000007
	print(ans)


for x in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	count = [0] * 50000
	per = 1
	prod = 1
	for s in a:
		count[s] += 1
	for x in count:
		per += x - 1
		if per <= 0:
			prod = 0
			break
		prod = prod * per % 1000000007
		n -= 1
		if n == 0:
			break
	print(prod)


mod = 1000000007

class FenwickTree:

	def __init__(self, N):
		self.data = [0] * (N + 1)
		self.size = N + 1

	def insert(self, i):
		if i == 0:
			self.data[0] += 1
			return
		while i < self.size:
			self.data[i] += 1
			i += i & -i

	def get_sum(self, i):
		result = self.data[0]
		while i > 0:
			result += self.data[i]
			i -= i & -i
		return result

def count_orderings(N, c):
	ft = FenwickTree(N)
	for ci in c:
		ft.insert(ci)
	result = 1
	for i in range(N):
		result = result * (ft.get_sum(i) - i) % mod
	return result
T = int(input())
for _ in range(T):
	N = int(input())
	c = [int(i) for i in input().split()]
	print(count_orderings(N, c))


def ways(n):
	res = 1
	n = sorted(n)
	for (i, val) in enumerate(n):
		ways = max(0, i + 1 - val)
		if ways > 0:
			res = res * ways % 1000000007
		else:
			return 0
	return res
for _ in range(int(input())):
	s = int(input())
	c = [int(x) for x in input().split()]
	print(ways(c))


from bisect import bisect
from functools import reduce

def cnt(c, n):
	c = sorted(c)
	count = reduce(lambda a, b: a * b, [bisect(c, i) - i for i in range(n)])
	return count % 1000000007
t = int(input())
for _ in range(t):
	n = int(input())
	c = [int(_) for _ in input().split()]
	print(cnt(c, n))


import collections, sys
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	c = list(map(int, sys.stdin.readline().split()))
	count = collections.Counter(c)
	n = 0
	combinations = 1
	possible_terms = 0
	while True:
		if n in count:
			possible_terms += count[n]
		if possible_terms > 0:
			combinations *= possible_terms
			combinations %= 1000000007
			possible_terms -= 1
			n += 1
		else:
			break
	print(0 if n < max(c) else combinations)


from collections import Counter
T = int(input())
for _ in range(T):
	N = int(input())
	cards = [int(ns) for ns in str(input()).split()]
	freq = Counter(cards)
	count = 1
	sc = 0
	for i in range(N):
		if i in freq:
			c = freq[i]
		else:
			c = 0
		sc += c
		if sc <= i:
			count = 0
			break
		count = count * (sc - i) % 1000000007
	print(count % 1000000007)


for _ in range(int(input())):
	n = int(input())
	xs = [int(i) for i in input().split()]
	fs = [0 for _ in range(n + 1)]
	for x in xs:
		fs[x] += 1
	if fs[n] > 0:
		print(0)
		continue
	p = 1
	r = 0
	for i in range(n):
		f = fs[i]
		p = p * (f + r) % 1000000007
		r += f - 1
	print(p)


def ways(array):
	buckets = {}
	for i in array:
		if i not in buckets:
			buckets[i] = 1
		else:
			buckets[i] += 1
	ways = 1
	count = 0
	for i in range(len(array)):
		if i in buckets:
			count += buckets[i]
		ways = ways * count % 1000000007
		count -= 1
		if count == -1:
			return 0
	return ways
for q in range(int(input())):
	input()
	print(ways([int(i) for i in input().split()]))


n = int(input())
for _ in range(n):
	numcards = int(input())
	cardvalues = [int(x) for x in input().split()]
	cardvalues.sort()
	ans = 1
	nc = 0
	for index in range(numcards):
		if cardvalues[index] > index:
			ans = 0
			break
		else:
			while nc < numcards and cardvalues[nc] <= index:
				nc += 1
			ans *= nc - index
			ans = ans % 1000000007
	print(ans)


for i in range(int(input())):
	N = int(input())
	coeffs = [int(j) for j in input().split()]
	coeffs.sort()
	i = 0
	res = 1
	for j in range(N):
		while i < N and coeffs[i] <= j:
			i += 1
		res *= i - j
		res %= 1000000007
	print(res)


modulus = 1000000007
for _ in range(int(input())):
	n = int(input())
	cards = sorted(map(int, input().split()))
	picked = 0
	i = 0
	numways = 1
	numoptions = 0
	while picked < n:
		while i < n and cards[i] <= picked:
			i += 1
			numoptions += 1
		numways *= numoptions
		numways = numways % modulus
		numoptions -= 1
		picked += 1
	print(numways)


t = int(input().strip())
for tt in range(t):
	p = int(input().strip())
	ar = [int(i) for i in input().strip().split()]
	counts = {}
	for x in ar:
		if x in counts:
			counts[x] = counts[x] + 1
		else:
			counts[x] = 1
	cs = 1
	ans = 1
	for i in range(0, p):
		if i in counts:
			cs = cs - 1 + counts[i]
		else:
			cs = cs - 1
		ans = ans * cs % 1000000007
	ans = ans % 1000000007
	print(ans)


def FindNumWays(N, C):
	freq = {}
	for c in C:
		if c not in freq:
			freq[c] = 1
		else:
			freq[c] += 1
	count = 0
	ways = 1
	for i in range(N):
		if i in freq:
			count += freq[i]
		ways *= count
		count -= 1
	return ways % 1000000007

def main():
	T = int(input())
	for t in range(T):
		N = int(input())
		C = input().split()
		C = [int(c) for c in C]
		print(FindNumWays(N, C))
main()


import collections, sys
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	c = list(map(int, sys.stdin.readline().split()))
	count = collections.Counter(c)
	n = 0
	combinations = 1
	possible_terms = 0
	while True:
		if n in count:
			possible_terms += count[n]
		if possible_terms > 0:
			combinations *= possible_terms
			combinations %= 1000000007
			possible_terms -= 1
			n += 1
		else:
			break
	print(0 if n < max(c) else combinations)


import collections, sys
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	c = list(map(int, sys.stdin.readline().split()))
	count = collections.Counter(c)
	n = 0
	combinations = 1
	possible_terms = 0
	while True:
		if n in count:
			possible_terms += count[n]
		if possible_terms > 0:
			combinations *= possible_terms
			combinations %= 1000000007
			possible_terms -= 1
			n += 1
		else:
			break
	print(0 if n < max(c) else combinations)


import collections, sys
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	c = list(map(int, sys.stdin.readline().split()))
	count = collections.Counter(c)
	n = 0
	combinations = 1
	possible_terms = 0
	while True:
		if n in count:
			possible_terms += count[n]
		if possible_terms > 0:
			combinations *= possible_terms
			combinations %= 1000000007
			possible_terms -= 1
			n += 1
		else:
			break
	print(0 if n < max(c) else combinations)


import sys
import collections

def solve(cs):
	counts = collections.defaultdict(int)
	for c in cs:
		counts[c] += 1
	num_pickables = collections.defaultdict(int)
	cum_sum = 0
	for i in range(50001):
		cum_sum += counts[i]
		num_pickables[i] = cum_sum
	num_picked = 0
	num_cards_remaining = len(cs)
	solution = 1
	while num_cards_remaining:
		num_pickable = num_pickables[num_picked] - num_picked
		if num_pickable:
			solution = solution * num_pickable % 1000000007
			num_cards_remaining -= 1
			num_picked += 1
		else:
			return 0
	return solution
T = int(sys.stdin.readline())
for case in range(T):
	_ = sys.stdin.readline()
	cs = [int(X) for X in sys.stdin.readline().split()]
	soln = solve(cs)
	print(soln, sep='')


for t in range(int(input())):
	n = int(input())
	data = sorted([int(x) for x in input().split()])
	r = 1
	available = 0
	i = ai = 0
	while ai >= i:
		while ai < n and data[ai] <= i:
			ai += 1
			available += 1
		if available == 0:
			break
		r *= available
		r %= 10 ** 9 + 7
		if r == 0:
			break
		available -= 1
		i += 1
	if i < n:
		r = 0
	print(r)


numTrials = int(input())

def card_pick(L):
	A = [0] * len(L)
	i = 0
	j = 0
	while i < len(L) and j < len(L):
		if L[i] <= j:
			A[j] += 1
			i += 1
		else:
			j += 1
			if j > 0 and j < len(L):
				A[j] = A[j - 1]
	for k in range(j + 1, len(L)):
		A[k] = A[k - 1]
	combo = 1
	for i in range(len(A)):
		combo = combo * (A[i] - i) % 1000000007
	return combo
for i in range(numTrials):
	elements = int(input())
	L = input().split()
	L = [int(i) for i in L]
	L.sort()
	print(card_pick(L))


from math import gamma
from math import exp

def pickcombin(N, strs):
	dict = {}
	n = 0
	total = 1
	for x in strs:
		if x in dict:
			dict[x] += 1
		else:
			dict[x] = 1
	for i in range(N):
		if i in dict:
			n = n + dict[i]
		if n - i < 1:
			return 0
		temp = n - i
		total *= temp % 1000000007
	return int(total % 1000000007)
t = int(input())
for _ in range(t):
	N = int(input())
	strs = input()
	strs = [int(x) for x in strs.split()]
	print(pickcombin(N, strs))


import collections, sys
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	c = list(map(int, sys.stdin.readline().split()))
	count = collections.Counter(c)
	n = 0
	combinations = 1
	possible_terms = 0
	while True:
		if n in count:
			possible_terms += count[n]
		if possible_terms > 0:
			combinations *= possible_terms
			combinations %= 1000000007
			possible_terms -= 1
			n += 1
		else:
			break
	print(0 if n < max(c) else combinations)


T = int(input())
for i in range(T):
	N = int(input())
	C = map(int, input().split())
	C = sorted(C)
	count = 1
	for j in range(N):
		number = j + 1
		if number - C[j] < 0:
			count = 0
			break
		else:
			count *= number - C[j]
			count %= 1000000007
	print(count)


def count_perms2(vals):
	vals = sorted(vals)
	nvals = len(vals)
	total = 1
	i = j = 0
	while i < nvals:
		while j < nvals and vals[j] <= i:
			j += 1
		total = total * (j - i) % 1000000007
		i += 1
	return total

def main():
	n = int(input().strip())
	for picked in range(n):
		nvals = int(input())
		vals = map(int, input().strip().split())
		print(count_perms2(vals))
main()


for t in range(int(input())):
	n = int(input())
	nums = sorted([int(x) for x in input().split()], reverse=True)
	ways = 1
	maxloc = n - 1
	try:
		for i in range(n):
			while maxloc > 0 and nums[maxloc - 1] <= i:
				maxloc -= 1
			ways *= n - i - maxloc
			ways %= 1000000007
			nums.pop()
	except:
		ways = 0
	print(ways)


def number_of_combinations(total_cards, cards):
	sorted_deck = sorted(cards, reverse=True)
	ways = 1
	for (i, card) in enumerate(sorted_deck):
		valids = total_cards - i - card
		if valids <= 0:
			return 0
		ways = ways * valids % 1000000007
	return ways
num_cases = int(input())
for case in range(num_cases):
	total_cards = int(input())
	cards = list(map(int, input().split()))
	print(number_of_combinations(total_cards, cards))


cases = int(input())
for i in range(cases):
	size = int(input())
	nums = map(int, input().split())
	table = []
	for i in range(size + 1):
		table.append(0)
	for i in nums:
		table[i] += 1
	total = 1
	sum = 0
	for i in range(size):
		sum += table[i]
		total = total * (sum - i) % 1000000007
	print(total)


import collections, sys
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	c = list(map(int, sys.stdin.readline().split()))
	count = collections.Counter(c)
	n = 0
	combinations = 1
	possible_terms = 0
	while True:
		if n in count:
			possible_terms += count[n]
		if possible_terms > 0:
			combinations *= possible_terms
			combinations %= 1000000007
			possible_terms -= 1
			n += 1
		else:
			break
	print(0 if n < max(c) else combinations)


def main():
	n = int(input().strip())
	for picked in range(n):
		nvals = int(input())
		vals = list(map(int, input().strip().split()))
		print(count_ways(vals))

def count_ways(vals):
	from collections import Counter
	counts = Counter(vals)
	playable = 0
	total = 1
	for i in range(len(vals)):
		playable += counts[i]
		if playable <= i:
			return 0
		total = total * (playable - i) % 1000000007
	return total
main()


def find_max_index(ls, item):
	length = len(ls)
	(low, high, res) = (0, length - 1, -1)
	while high >= low:
		middle = (high + low) // 2
		if ls[middle] <= item:
			res = middle
			low = middle + 1
		else:
			high = middle - 1
	return res

def pick_card(ls):
	ls.sort()
	res = 1
	for (i, item) in enumerate(ls):
		if item >= i + 1:
			return 0
		max_index = find_max_index(ls, i)
		res = (max_index - i + 1) * res % 1000000007
	return res
t = int(input())
for _ in range(t):
	k = int(input())
	l = list(map(int, input().split()))
	res = pick_card(l)
	print(res)


from collections import defaultdict as ddict
for _ in range(int(input())):
	N = int(input())
	L = [int(i) for i in input().split()]
	L2 = ddict(lambda : 0)
	for l in L:
		L2[l] += 1
	res = 0
	nb = 1
	for i in range(N):
		if i in L2:
			res += L2[i]
		nb = nb * res % 1000000007
		res -= 1
		if nb == 0:
			break
	print(nb)


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

def all_cards(N, c):
	c.sort()
	ways = 1
	cum_options = 0
	for i in range(N):
		while len(c) != 0 and c[0] == i:
			cum_options += 1
			c.pop(0)
		ways = ways * (cum_options - i) % 1000000007
	print(ways)
for i in range(T):
	N = int(input())
	c = [int(card) for card in input().split()]
	all_cards(N, c)


modulo = 1000000007

def new_binary_search(arr, key, head):
	mid = head + len(arr) - 1 >> 1
	if arr[mid] <= key:
		head = mid
	else:
		return head
	return binary_search(arr, key, head, tail)

def hallo(c, N):
	prod = 1
	for cnt in range(N - 1, -1, -1):
		if c[cnt] > cnt:
			return 0
		prod *= cnt - c[cnt] + 1
		prod %= modulo
	return prod
T = int(input())
for tmp in range(T):
	N = int(input())
	c = list(map(int, input().strip().split(' ')))
	c.sort()
	print(hallo(c, N))


T = int(input())
for i in range(T):
	N = int(input())
	l = sorted(list(map(int, input().strip().split())))
	result = 1
	for j in range(N):
		if j < l[j]:
			result = 0
			break
		else:
			result *= j + 1 - l[j]
	print(result % 1000000007)


import collections, sys
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	c = list(map(int, sys.stdin.readline().split()))
	count = collections.Counter(c)
	n = 0
	combinations = 1
	possible_terms = 0
	while True:
		if n in count:
			possible_terms += count[n]
		if possible_terms > 0:
			combinations *= possible_terms
			combinations %= 1000000007
			possible_terms -= 1
			n += 1
		else:
			break
	print(0 if n < max(c) else combinations)


t = int(input())
for test in range(t):
	n = int(input())
	l = [int(x) for x in input().split()]
	m = [0 for i in range(n)]
	k = 0
	for x in l:
		if x == 0:
			k += 1
		if x != 0 and x < n:
			m[x] += 1
	p = 1
	q = k + 1
	for i in range(n):
		q += m[i] - 1
		p = p * q % 1000000007
	print(p)


def num_zeros(x):
	rv = 0
	pos = -1
	for i in range(len(x)):
		if x[i] == 0:
			rv += 1
			pos = i
	return (rv, pos)

def num_orders(x):
	if len(x) == 0:
		return 1
	(count, pos) = num_zeros(x)
	if count == 0:
		return 0
	sub = x[:pos] + x[pos + 1:]
	sub_red = [max(0, t - 1) for t in sub]
	return count * num_orders(sub_red) % 1000000007

def num_orders2(x):
	n = len(x)
	freq = [0 for i in range(n + 1)]
	for t in x:
		freq[t] += 1
	prod = 1
	avail = 1
	for i in range(n):
		avail += freq[i] - 1
		if avail <= 0:
			return 0
		prod = prod * avail % 1000000007
	return prod
num_probs = int(input())
for i in range(num_probs):
	nn = int(input())
	x = [int(i) for i in input().split()]
	print(num_orders2(x))


T = int(input())

def histogram(N, arr):
	hist = [0] * (N + 1)
	for i in range(N):
		hist[arr[i]] += 1
	return hist

def main(N, hist):
	Ways = 1
	Sum_temp = hist[0]
	for i in range(N):
		Ways *= (Sum_temp - i) % 1000000007
		Ways = Ways % 1000000007
		if Ways == 0:
			return 0
		Sum_temp += hist[i + 1]
	return Ways
for i in range(T):
	N = int(input())
	args = input()
	Cards = [int(x) for x in args.split()]
	print(main(N, histogram(N, Cards)))


LARGE = 1000000007
cache = {}

def nPr(n, r):
	if not (n, r) in cache:
		ans = 1
		for i in range(n - r + 1, n + 1):
			ans *= i
		cache[n, r] = ans
	return cache[n, r]
T = int(input())
for t in range(T):
	n = int(input())
	A = list(map(int, input().strip().split(' ')))
	B = [0 for i in range(n + 1)]
	ans = 1
	A.sort()
	for i in range(n):
		B[A[i]] += 1
	for i in range(n):
		ans *= max(0, i + 1 - A[i])
	print(ans % LARGE)


from os.path import basename, exists, expanduser, splitext, isfile
from os import getcwd
from sys import stdin
from array import array as ar
from collections import Counter
from functools import reduce as red
import itertools as it
from itertools import accumulate as acc, permutations as per
lolPath = getcwd()
randid = '\\qosdjfoiz.txt'
home = isfile(lolPath + randid)

def inv(n):
	return pow(n, modo - 2, modo)
if home:
	filou = lolPath + '\\PickingCards20.txt'
	filin = 'D:\\ZeDaddy\\Documents\\Hack\\combinatorics\\JourneyOu03.txt'
	from mesures import ch
else:
	filou = None
modo = 10 ** 9 + 7
trace = 0

def cntLow(A):
	cnt = sorted(Counter(A).items())
	tbLow = [0] * len(A)
	(ix, ev) = (0, 0)
	prd = 1
	for (val, nb) in cnt:
		while ix < val:
			prd = prd * (ev - ix) % modo
			ix += 1
		ev += nb
		prd = prd * (ev - ix) % modo
		ix += 1
	while ix < len(A):
		prd = prd * (ev - ix) % modo
		ix += 1
	return prd
trace = 0
if home:
	from mesures import ch, prof
rd = open(filou) if filou else stdin
for _ in range(int(rd.readline().strip())):
	rd.readline()
	A = sorted(map(int, rd.readline().strip().split()))
	if home:
		print(A[:40])
	for f in (cntLow,):
		if home:
			cr = ch()
		r = f(A)
		if home:
			t = cr.lap()
			print(f.__name__, r, t)
		else:
			print(r)


for i in range(int(input())):
	n = int(input())
	c = [int(j) for j in input().split()]
	c.sort(reverse=True)
	a = 1
	for k in range(n):
		a *= n - k - c[k]
	print(a % 1000000007)


from bisect import bisect_right

class Finder:

	def __init__(self, arr):
		self.prev = []
		self.arr = arr

	def find_gt(self, x, low):
		if self.prev and self.prev[0] > x:
			return prev[1]
		else:
			i = bisect_right(self.arr, x, low)
			prev = [self.arr[-1], n] if i == n else [self.arr[i], i]
			return prev[1]
for _ in range(int(input())):
	n = int(input())
	arr = sorted([int(x) for x in input().split()])
	r = 1
	f = Finder(arr)
	for i in range(n):
		r *= (f.find_gt(i, i) - i) % 1000000007
		r %= 1000000007
		if r == 0:
			break
	print(r)


from functools import reduce
for _ in range(int(input())):
	counter = [0] * (int(input()) + 1)
	for i in map(int, input().split()):
		counter[i] += 1
	for i in range(1, len(counter)):
		counter[i] += counter[i - 1] - 1
	print(0 if any(map(lambda x: x <= 0, counter[:-1])) else reduce(lambda x, y: x * y % 1000000007, counter[:-1]))


def readProblemConsole():
	tests = []
	numTests = int(input())
	for _ in range(numTests):
		N = int(input())
		test = input()
		test.strip()
		test = test.split()
		assert len(test) == N
		test_a = [0 for _ in range(N + 1)]
		for t in test:
			test_a[int(t)] += 1
		tests.append(test_a)
	return tests

def countPossibilies(test):
	N = 1
	sum_v = 0
	for i in range(len(test) - 1):
		sum_v += test[i]
		N = N * sum_v % 1000000007
		sum_v -= 1
	return N
tests = readProblemConsole()
for test in tests:
	print(countPossibilies(test))


t = int(input().strip())
for _ in range(t):
	N = int(input().strip())
	cards = [int(x) for x in input().strip().split(' ')]
	count = [0] * (N + 1)
	for card in cards:
		count[card] += 1
	perms = count[0]
	remain = count[0] - 1
	for i in range(1, N):
		if perms == 0:
			break
		perms *= count[i] + remain
		perms = perms % 1000000007
		remain += count[i] - 1
	print(perms)


def factorial(x, mod=10 ** 9 + 7):
	ans = 1
	for y in range(1, x + 1):
		ans = ans % mod * (y % mod) % mod
	return ans
t = int(input().strip())
for i in range(t):
	n = int(input().strip())
	list_of_cards = [int(x) for x in input().strip().split()]
	card_values = [0] * (max(list_of_cards) + 1)
	for ci in list_of_cards:
		card_values[ci] += 1
	factor = 0
	ans = 1
	for (i, ci) in enumerate(card_values[:-1]):
		factor += ci
		ans = factor % (10 ** 9 + 7) * (ans % (10 ** 9 + 7)) % (10 ** 9 + 7)
		factor -= 1
	ans = factorial(factor + card_values[-1]) * (ans % (10 ** 9 + 7)) % (10 ** 9 + 7)
	print(ans)


import sys
import math
t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	cards = [int(i) for i in input().strip().split()]
	cards.sort()
	n_picks = 0
	n_ways = 1
	i = 0
	j = 0
	while True:
		if j == len(cards) or n_picks < cards[j]:
			count = j - i
			if count == 0:
				n_ways = 0
				break
			else:
				if j == len(cards):
					n_ways *= math.factorial(count)
					break
				n_ways *= count
				n_picks += 1
				i += 1
		else:
			j += 1
	print(n_ways % 1000000007)


for i in range(int(input())):
	input()
	lst = [int(i) for i in input().split()]
	lst.sort()
	x = [0 for i in range(len(lst) + 1)]
	for i in lst:
		x[i] += 1
	for i in range(1, len(x)):
		x[i] += x[i - 1]
	s = 1
	for i in range(len(x) - 1):
		s = s * (x[i] - i) % (10 ** 9 + 7)
		if s == 0:
			break
	print(s)


mod = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	A = [0] * (n + 1)
	for i in input().strip().split():
		A[int(i)] += 1
	for i in range(1, n + 1):
		A[i] += A[i - 1] - 1
	res = 1
	for a in A[:-1]:
		res = res * a % mod
	print(res)


P = 1000000007
factors = [1]
for i in range(1, 50001):
	factors.append(factors[-1] * i % P)
T = int(input())
for i in range(T):
	res = 1
	N = int(input())
	c_str = input().split()
	c = {}
	l = len(c_str)
	for j in c_str:
		if int(j) in c:
			c[int(j)] += 1
		else:
			c[int(j)] = 1
	possible = 0
	for j in range(N):
		try:
			possible += c[j]
		except:
			possible += 0
		if possible == l:
			res = res * factors[possible - j] % P
			break
		if possible <= j:
			res = 0
			break
		res *= (possible - j) % P
	print(res)


tests = int(input())
for test in range(tests):
	n = int(input())
	cards = list(map(int, input().split()))
	mod = 10 ** 9 + 7
	counts = [0] * (n + 1)
	for card in cards:
		counts[card] += 1
	total = 1
	options = counts[0]
	for i in range(1, n + 1):
		total = total * options % mod
		options += counts[i] - 1
	print(total)


inf = float('inf')
read_ints = lambda : list(map(int, input().split()))

def solve(N, C):
	H = {}
	for c in C:
		H[c] = H.get(c, 0) + 1
	P = [0] * N
	acum = 0
	for i in range(N):
		acum += H.get(i, 0)
		P[i] = acum
	ans = 1
	for i in range(N):
		ans = ans * (P[i] - i) % 1000000007
	return ans
T = int(input())
for _ in range(T):
	N = int(input())
	arr = read_ints()
	print(solve(N, arr))


tests = int(input())
for t in range(tests):
	n = int(input())
	nms = sorted(list(map(int, input().split())))
	nums = [0 for i in range(n + 1)]
	flag = False
	for i in nms:
		if i > n:
			flag = True
			break
		nums[i] += 1
	if flag:
		continue
	res = 1
	opts = 0
	for i in nums[:-1]:
		if opts == 0 and i == 0:
			res = 0
			break
		opts += i
		res *= opts
		res = res % 1000000007
		opts -= 1
	while opts > 1:
		res *= opts
		res = res % 1000000007
		opts -= 1
	print(res)


cases = int(input())
for i in range(cases):
	n = int(input())
	b = input().split()
	ls = [0] * (n + 1)
	for j in b:
		ls[int(j)] += 1
	options = ls[0]
	total = 1
	for z in range(1, n):
		total = total * options % 1000000007
		options = options - 1 + ls[z]
	print(total)


from collections import defaultdict
cases = int(input())
while cases:
	total = 1
	num = int(input())
	l = [int(x) for x in input().split()]
	count = 0
	d = defaultdict(int)
	for j in l:
		d[j] += 1
	for j in range(num):
		count = count + d[j]
		total = total * count % 1000000007
		count = count - 1
		d[j] = 0
	d[j] = 0
	print(total)
	cases -= 1


t = int(input())
for x in range(t):
	n = int(input())
	l = [int(y) for y in input().strip().split(' ')]
	ls = [0 for y in range(n + 1)]
	for y in l:
		ls[y] += 1
	(s, r) = (1, 0)
	for y in range(n):
		s = s * (ls[y] + r) % 1000000007
		r = r + ls[y] - 1
	print(s)


T = int(input())
for _ in range(T):
	N = int(input())
	nums = [int(x) for x in input().split()]
	cards = {}
	for i in range(N + 1):
		cards[i] = 0
	ways = 1
	summ = 0
	for c in nums:
		cards[c] += 1
	for i in range(N):
		summ += cards[i]
		ways = ways * summ % 1000000007
		if ways == 0:
			break
		summ -= 1
	print(ways)


T = int(input())
for _ in range(T):
	N = int(input())
	nums = [int(x) for x in input().split()]
	cards = {}
	for i in range(N + 1):
		cards[i] = 0
	ways = 1
	summ = 0
	for c in nums:
		cards[c] += 1
	for i in range(N):
		summ += cards[i]
		ways = ways * summ % 1000000007
		if ways == 0:
			break
		summ -= 1
	print(ways)


B = 1000000007
t = int(input())
while t != 0:
	t -= 1
	f = [0] * 100005
	n = int(input())
	a = [int(x) for x in input().split()]
	for i in a:
		f[i] += 1
	rs = f[0]
	for i in range(1, n):
		f[i] = (f[i] + f[i - 1]) % B
		rs = rs * (f[i] - i) % B
	print(rs)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	d = {}
	for i in range(n + 1):
		d[i] = 0
	for i in a:
		d[i] += 1
	summ = 0
	ways = 1
	for i in range(n):
		summ += d[i]
		ways = ways * summ % 1000000007
		summ -= 1
		if ways == 0:
			break
	print(ways)


mod = 1000000007
t = int(input())

def cards(t, mod):
	while t > 0:
		t -= 1
		n = int(input())
		lis = [int(a) for a in input().strip().split()]
		total = len(lis)
		counter = [0] * 50001
		current = 0
		for items in lis:
			counter[items] += 1
		ways = 1
		picked = 0
		avail = 0
		if counter[0] == 0:
			print(0)
			continue
		while n > picked and counter[0] != 0:
			if counter[picked] == 0 and picked > 0:
				ways *= avail
				ways %= mod
				picked += 1
			elif counter[picked] != 0:
				avail += counter[picked]
				ways *= avail
				ways %= mod
				picked += 1
			avail -= 1
		if ways > 0:
			print(ways)
		else:
			print(0)
cards(t, mod)


for _ in range(int(input())):
	N = int(input())
	nums = [int(x) for x in input().split()]
	cards = {}
	for i in range(N + 1):
		cards[i] = 0
	ways = 1
	summ = 0
	for c in nums:
		cards[c] += 1
	for i in range(N):
		summ += cards[i]
		ways = ways * summ % 1000000007
		if ways == 0:
			break
		summ -= 1
	print(ways)


T = int(input())
F = {}

def fac(n):
	if n <= 1:
		return 1
	if n in F:
		return F[n]
	t = n * fac(n - 1) % (10 ** 9 + 7)
	F[n] = t
	return t
for t0 in range(T):
	N = int(input())
	A = [int(a) for a in input().split()]
	A.sort()
	C = {}
	c = 1
	for i in range(1, len(A)):
		if A[i - 1] != A[i]:
			C[A[i - 1]] = c
			c = 1
		else:
			c += 1
	C[A[-1]] = c
	m = A[-1]
	s = 1
	p = 0
	for i in range(N):
		if i in C:
			p += C[i]
		if (i < m) & (p == 0):
			s = 0
			break
		s *= p
		s = s % (10 ** 9 + 7)
		p -= 1
	print(s)