*"We’ve already come too far to end this now".*

N players advance to the fifth round and the game is going to be Hopscotch. Every player has to select one mannequin before the start of the game.

Players are numbered 1 to N. You are given an array A of size N, where    
* If A_{i} = i, the i^{\text{th}} player selects their own mannequin.
* If A_{i} = j where j \neq i, the i^{\text{th}} player decides the mannequin for the j^{\text{th}} player.
* If A_{i} = 0, the i^{\text{th}} player hasn’t decided yet.

The VIPs want to know the number of ways that the undecided players can select mannequins such that everyone gets a mannequin, and no undecided players select their own mannequin.

It is guaranteed that every (non-zero) element in A is unique, i.e, if 1 ≤ i, j ≤ N are such that i \neq j, A_{i} > 0, and A_{j} > 0, then A_{i} \neq A_{j}.

Since the answer can be very large, print it modulo 10^{9} + 7.

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

- The first line of 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 a single integer N denoting the number of players.    
- The second line contains N space-separated integers, the i^{\text{th}} of which is A_{i} as described in the statement above.

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

For every test case, print one line containing the number of ways undecided players can select mannequins for others such that everyone receives a mannequin, modulo 10^{9}+7.

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

$1 ≤ T ≤ 10^{3}$
$1 ≤ N ≤ 10^{3}$
$0 ≤ A_{i} ≤ N$
- The non-zero elements of $A$ are distinct.

----- Sample Input 1 ------ 
3    
5    
1 2 3 4 5    
6    
3 6 1 0 0 0    
10    
0 0 0 0 0 0 0 0 0 0
----- Sample Output 1 ------ 
0    
3    
1334961
----- explanation 1 ------ 
Test Case 1: There is no undecided player, so the number of ways is $0$.

Test Case 2: There are $3$ ways for the last $3$ players to decide mannequins, all of which are listed below:
- $4 \rightarrow 2 , 5 \rightarrow 4, 6 \rightarrow 5$
- $4 \rightarrow 5 , 5 \rightarrow 4, 6 \rightarrow 2$
- $4 \rightarrow 5 , 5 \rightarrow 2, 6 \rightarrow 4$

where $a \rightarrow b$ means that $a$ selects the mannequin for $b$.

Source: codechef | Difficulty: VERY_HARD
Tags: Dynamic programming

Combinatorics

Mathematics


Solutions:
N = 1001
factorialNumInverse = [None] * (N + 1)
naturalNumInverse = [None] * (N + 1)
fact = [None] * (N + 1)

def InverseofNumber(p):
	naturalNumInverse[0] = naturalNumInverse[1] = 1
	for i in range(2, N + 1, 1):
		naturalNumInverse[i] = naturalNumInverse[p % i] * (p - int(p / i)) % p

def InverseofFactorial(p):
	factorialNumInverse[0] = factorialNumInverse[1] = 1
	for i in range(2, N + 1, 1):
		factorialNumInverse[i] = naturalNumInverse[i] * factorialNumInverse[i - 1] % p

def factorial(p):
	fact[0] = 1
	for i in range(1, N + 1):
		fact[i] = fact[i - 1] * i % p

def Binomial(N, R, p):
	ans = fact[N] * factorialNumInverse[R] % p * factorialNumInverse[N - R] % p
	return ans
p = 1000000007
InverseofNumber(p)
InverseofFactorial(p)
factorial(p)
t = int(input())
for tt in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	aa = [0] * n
	p1 = 0
	q1 = 0
	for r in range(n):
		if a[r] != 0:
			aa[a[r] - 1] = 1
	for rr in range(n):
		if a[rr] == 0:
			if aa[rr] == 0:
				q1 += 1
			else:
				p1 += 1
	if p1 == 0 and q1 == 0:
		print(0)
		continue
	ans = fact[p1 + q1]
	if q1 == 0:
		print(ans)
		continue
	for rrr in range(1, q1 + 1):
		if rrr & 1 == 0:
			ans = (ans + Binomial(q1, rrr, p) * fact[p1 + q1 - rrr] % p) % p
		else:
			ans = (ans - Binomial(q1, rrr, p) * fact[p1 + q1 - rrr] % p) % p
	print(ans)


N = 1000
mod = 10 ** 9 + 7
fact = [1 for i in range(N + 1)]
inv = [1 for i in range(N + 1)]
val = 1
for i in range(1, N + 1):
	val = val * i % mod
	fact[i] = val
	inv[i] = pow(fact[i], mod - 2, mod)

def nCr(n, r):
	return fact[n] * inv[r] * inv[n - r] % mod
p = 10 ** 9 + 7
t = int(input())
for tt in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	aa = [0] * n
	p1 = 0
	q1 = 0
	for r in range(n):
		if a[r] != 0:
			aa[a[r] - 1] = 1
	for rr in range(n):
		if a[rr] == 0:
			if aa[rr] == 0:
				q1 += 1
			else:
				p1 += 1
	if p1 == 0 and q1 == 0:
		print(0)
		continue
	ans = fact[p1 + q1]
	for rrr in range(1, q1 + 1):
		if rrr & 1 == 0:
			ans = (ans + nCr(q1, rrr) * fact[p1 + q1 - rrr] % p) % p
		else:
			ans = (ans - nCr(q1, rrr) * fact[p1 + q1 - rrr] % p) % p
	print(ans)


import math, sys
input = sys.stdin.readline
S = lambda : input().rstrip()
I = lambda : int(S())
M = lambda : map(int, S().split())
L = lambda : list(M())
mod1 = 1000000007
mod2 = 998244353
fact = [1] * 10000
for i in range(1, 10000):
	fact[i] = fact[i - 1] * i % mod1
for _ in range(I()):
	n = I()
	a = L()
	s1 = set()
	s2 = set()
	s3 = set()
	if 0 not in a:
		print(0)
		continue
	for i in range(n):
		if a[i] == 0:
			s1.add(i + 1)
		else:
			s2.add(a[i])
	for i in range(1, n + 1):
		if i not in s2:
			s3.add(i)
	k = len(s1 & s3)
	t = len(s1)
	ans = fact[t]
	for i in range(1, k + 1):
		p = fact[k] * pow(fact[k - i], mod1 - 2, mod1) * pow(fact[i], mod1 - 2, mod1) * fact[t - i] % mod1
		if i % 2 == 1:
			ans = (ans - p) % mod1
		else:
			ans = (ans + p) % mod1
	print(ans)