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: interview

Starter code:

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


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


mod = int(1e9) + 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=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)


# cook your dish here
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)

MOD = 10**9 + 7

def ncr(n, r):
 num = den = 1
 for i in range(r):
  num = (num * (n - 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)
 


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)))

 rem = m - n + 1

 ans = (ans * ncr(total, rem)) % 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 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)

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(k>n-1):
  t=k-(n-1)
  if(t>ex):
   ans=0 
  else:
   ans=((ans*facto(ex))%m*(ifacto(t)*ifacto(ex-t))%m)%m
 print(ans)

import sys
import math
from collections import defaultdict,Counter

input=sys.stdin.readline
def print(x):
 sys.stdout.write(str(x)+"\n")

# sys.stdout=open("CP1/output.txt",'w')
# sys.stdin=open("CP1/input.txt",'r')

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)


import sys
import math
from collections import defaultdict,Counter

input=sys.stdin.readline
def print(x):
 sys.stdout.write(str(x)+"\n")

# sys.stdout=open("CP1/output.txt",'w')
# sys.stdin=open("CP1/input.txt",'r')

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)


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)

import sys
import math
from collections import defaultdict,Counter

# input=sys.stdin.readline
# def print(x):
#     sys.stdout.write(str(x)+"\n")

# sys.stdout=open("CP3/output.txt",'w')
# sys.stdin=open("CP3/input.txt",'r')

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
  #   if c[j]>c.get(j-1,0):
  #       ans=0
  #       break
  #   cur=1
  #   for k in range(c[j-1],c[j-1]-c[j],-1):
  #       cur=(cur*k)%m
  #   ans=(ans+cur)%m
  # if max(c)==1:
  #   ans=1
  print(ans)
 else:
  print(0)

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)%m
 print(ans)

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)