One day, Tanya was studying graph theory. She is very inquisitive, so the following problem soon came to her mind.
Find the number of undirected unweighted connected simple graphs with $N$ vertices (numbered $1$ through $N$) and $M$ edges, such that for each $i$ ($2 \le i \le N$), the shortest path from vertex $1$ to vertex $i$ is unique and its length is equal to $A_i$. In other words, for each $i$ ($2 \le i \le N$), there should be exactly one path with length $A_i$ between vertices $1$ and $i$, and there should be no paths with smaller length between these vertices.
Two graphs with $N$ vertices are distinct if we can find two vertices $u$ and $v$ such that there is an edge between these vertices in one graph, but not in the other graph.
Since the answer could be very large, compute it modulo $1,000,000,007$ ($10^9 + 7$).

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains two space-separated integers $N$ and $M$.
- The second line contains $N - 1$ space-separated integers $A_2, A_3, \ldots, A_N$.

-----Output-----
For each test case, print a single line containing one integer ― the number of graphs modulo $10^9 + 7$.

-----Constraints-----
- $1 \le T \le 1,000$
- $2 \le N \le 10^5$
- $N-1 \le M \le \mathrm{min}\left(2\cdot 10^5, \frac{N(N-1)}{2}\right)$
- $1 \le A_i \le N-1$ for each valid $i$
- the sum of $N$ over all test cases does not exceed $2 \cdot 10^5$
- the sum of $M$ over all test cases does not exceed $2 \cdot 10^5$

-----Subtasks-----
Subtask #1 (50 points): $M = N-1$
Subtask #2 (50 points): original constraints

-----Example Input-----
3
4 3
1 2 1
4 6
1 2 1
3 2
2 2

-----Example Output-----
2
0
0

-----Explanation-----
Example case 1: The two graphs which satisfy all conditions are:

Difficulty: VERY_HARD
Tags: Graph algorithms

Combinatorics

Number theory

Mathematics

Data structures
Skill types: Data structures

Starter code:

Solutions:
def multiple_input():
	return map(int, input().split())

def list_input():
	return list(map(int, input().split()))
mod = int(1000000000.0) + 7
for _ in range(int(input())):
	(n, m) = multiple_input()
	a = list_input()
	a.sort()
	max_level = a[-1] + 1
	levels = [0] * max_level
	levels[0] = 1
	for i in a:
		levels[i] += 1
	ans = 1
	for i in range(1, max_level):
		ans = ans * pow(levels[i - 1], levels[i], mod) % mod
	print(ans)


MOD = 10 ** 9 + 7
T = int(input())
for t in range(T):
	(n, m) = map(int, input().split())
	A = list(map(int, input().split()))
	mp = [0] * n
	for a in A:
		mp[a] += 1
	mx = max(A)
	ans = 1
	for i in range(1, mx):
		ans = ans * mp[i] ** mp[i + 1] % MOD
	print(ans)


MOD = 10 ** 9 + 7

def ncr(n, r):
	num = den = 1
	for i in range(r):
		num = num * (num - i) % MOD
		den = den * (i + 1) % MOD
	return num * pow(den, MOD - 2, MOD) % MOD
for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	d = {0: 1}
	for i in a:
		d[i] = 1 if i not in d else d[i] + 1
	ans = 1
	total = 0
	for (i, j) in list(d.items()):
		if i == 0:
			continue
		ans = ans * pow(d[i - 1] if i - 1 in d else 0, j, MOD) % MOD
		total = (total + j * (j - 1) // 2 % MOD) % MOD
	rem = m - n + 1
	ans = ans * ncr(total, rem) % MOD
	print(ans)


from functools import reduce
from collections import Counter
mod = 1000000007

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a):
	(g, x, y) = egcd(a, mod)
	return x % mod

def mul(x, y):
	return x * y % mod

def ncr(n, r):
	r = min(r, n - r)
	numer = reduce(mul, range(n, n - r, -1), 1)
	denom = reduce(mul, map(modinv, range(1, r + 1)), 1)
	return numer * denom
t = int(input())
for ti in range(t):
	(n, m) = map(int, input().split())
	counts = Counter(map(int, input().split()))
	res = 1
	previ = 1
	prevc = 1
	free = 0
	fail = False
	for i in range(1, len(counts) + 1):
		if i not in counts:
			fail = True
			break
		for j in range(counts[i]):
			res *= prevc
			res %= mod
		prevc = counts[i]
		free += prevc * (prevc - 1) // 2
	extra = m - n + 1
	if fail or extra > free:
		print(0)
		continue
	res *= ncr(free, extra)
	print(res % mod)


mod = pow(10, 9) + 7
for tt in range(int(input())):
	(n, m) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	d = [0 for i in range(n + 1)]
	for i in l:
		d[i] += 1
	ans = 1
	for i in range(2, n + 1):
		ans *= pow(d[i - 1], d[i])
		ans %= mod
	print(ans % mod)


import sys
import math
from collections import defaultdict, Counter
m = pow(10, 9) + 7
t = int(input())
for i in range(t):
	(n, m1) = map(int, input().split())
	a = list(map(int, input().split()))
	if m1 == n - 1:
		ans = 1
		c = Counter(a)
		for j in c:
			if j == 1:
				continue
			ans = ans * pow(c.get(j - 1, 0), c[j], m) % m
		print(ans)
	else:
		print(0)


from collections import defaultdict
m = pow(10, 9) + 7

def inv(i):
	return pow(i, m - 2, m)

def ifacto(n):
	if n > len(ifact) - 1:
		for i in range(len(ifact), n + 1):
			temp = inv(i) * ifact[i - 1] % m
			ifact.append(temp)
	return ifact[n]

def facto(n):
	if n > len(fact) - 1:
		for i in range(len(fact), n + 1):
			temp = i * fact[i - 1] % m
			fact.append(temp)
	return fact[n]
fact = [1]
ifact = [1]
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	d = defaultdict(int)
	d[0] = 1
	ans = 1
	ex = 0
	for i in a:
		d[i] = d[i] + 1
	for i in range(1, max(a) + 1):
		ans = ans * pow(d[i - 1], d[i], m) % m
		ex = ex + int(d[i] * (d[i] - 1) / 2)
		if ans == 0:
			break
	if k > n - 1 and ans != 0:
		t = k - (n - 1)
		if t > ex:
			ans = 0
		else:
			ans = ans * facto(ex) % m * (ifacto(t) * ifacto(ex - t)) % m % m
	print(ans)


for _ in range(int(input())):
	(n, m) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	a.sort()
	f = 1
	m = 10 ** 9 + 7
	d = [0 for i in range(n)]
	for i in a:
		d[i] += 1
	for i in range(2, n):
		f *= d[i - 1] ** d[i]
		f %= m
	print(f)


from collections import defaultdict

def factorial(n):
	if n < 0:
		return 0
	elif n == 0 or n == 1:
		return 1
	else:
		fact = 1
		while n > 1:
			fact *= n
			n -= 1
		return fact
m = pow(10, 9) + 7
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	d = defaultdict(int)
	d[0] = 1
	ans = 1
	ex = 0
	for i in a:
		d[i] = d[i] + 1
	for i in range(1, max(a) + 1):
		ans = ans * pow(d[i - 1], d[i], m) % m
		ex = ex + int(d[i] * (d[i] - 1) / 2)
	if k > n - 1:
		t = k - (n - 1)
		if t > ex:
			ans = 0
		else:
			ans = ans * factorial(ex) / factorial(ex - t) * factorial(t) % m
	print(ans)


mod = 10 ** 9 + 7
from math import factorial

def create_dic(array):
	dic = {}
	for i in array:
		if i in dic:
			dic[i] += 1
		else:
			dic[i] = 1
	return dic

def C(n, r):
	if r > n:
		return 0
	elif r == n:
		return 1
	elif r == 0:
		return 1
	r = max(r, n - r)
	num = 1
	for i in range(r + 1, n + 1):
		num = num * i % mod
	den = 1
	for i in range(1, n - r + 1):
		den = den * i % mod
	tbm = pow(den, mod - 2, mod)
	num = num * tbm % mod
	return num
for _ in range(int(input())):
	(N, M) = map(int, input().split())
	array = list(map(int, input().split()))
	total = 0
	if M >= N - 1:
		dic = create_dic(array)
		if 1 in dic.keys():
			possible = True
			cnt = dic[1]
			search = 2
			total = 1
			while cnt < N - 1 and possible:
				if search in dic.keys():
					total = total * pow(dic[search - 1], dic[search], mod) % mod
					cnt += dic[search]
					search += 1
				else:
					possible = False
					total = 0
		else:
			total = 0
	if total > 0:
		left = M - N + 1
		pis = 0
		for value in dic.values():
			pis += value * (value - 1) // 2
		total = total * C(pis, left) % mod
	print(total)


import sys
import math
from collections import defaultdict, Counter
input = sys.stdin.readline

def print(x):
	sys.stdout.write(str(x) + '\n')

def power(x, y, m):
	if y == 0:
		return 1
	p = power(x, y // 2, m) % m
	p = p * p % m
	if y % 2 == 0:
		return p
	else:
		return x * p % m

def find(n, r):
	p = 1
	q = 1
	for j in range(1, r + 1):
		p = p * (n - j + 1) % m
		q = q * j % m
	return p * power(q, m - 2, m) % m
m = pow(10, 9) + 7
t = int(input())
for i in range(t):
	(n, m1) = map(int, input().split())
	a = list(map(int, input().split()))
	avail = 0
	req = m1 - (n - 1)
	ans = 1
	c = Counter(a)
	for j in c:
		avail += c[j] * (c[j] - 1) // 2
		if j == 1:
			continue
		ans = ans * pow(c.get(j - 1, 0), c[j], m) % m
	if req > avail:
		print(0)
	else:
		ans = ans * find(avail, req) % m
		print(ans)


def inv(x):
	return pow(x, 1000000005, 1000000007)

def nCr(n, r):
	z = 1
	for i in range(r):
		z = z * (n - i)
		z %= 1000000007
	for i in range(r):
		z = z * inv(i + 1)
		z %= 1000000007
	return z
t = int(input())
for you in range(t):
	l = input().split()
	n = int(l[0])
	m = int(l[1])
	l = input().split()
	li = [int(i) for i in l]
	hashi = dict()
	freq = [0 for i in range(n - 1)]
	for i in li:
		freq[i - 1] += 1
	pro = 1
	count = 0
	curr = 1
	for i in range(n - 1):
		if freq[i] == 0:
			break
		pro = pro * pow(curr, freq[i], 1000000007)
		pro %= 1000000007
		count += freq[i]
		curr = freq[i]
	if count != n - 1:
		print(0)
		continue
	m -= n - 1
	tota = 0
	for i in freq:
		tota += i * (i - 1) // 2
	if tota < m:
		print(0)
	else:
		z = nCr(tota, m)
		pro *= z
		pro %= 1000000007
		print(pro)