You are given a permutation $a_1,a_2,\ldots,a_n$ of integers from $0$ to $n - 1$. Your task is to find how many permutations $b_1,b_2,\ldots,b_n$ are similar to permutation $a$.

Two permutations $a$ and $b$ of size $n$ are considered similar if for all intervals $[l,r]$ ($1 \le l \le r \le n$), the following condition is satisfied: $$\operatorname{MEX}([a_l,a_{l+1},\ldots,a_r])=\operatorname{MEX}([b_l,b_{l+1},\ldots,b_r]),$$ where the $\operatorname{MEX}$ of a collection of integers $c_1,c_2,\ldots,c_k$ is defined as the smallest non-negative integer $x$ which does not occur in collection $c$. For example, $\operatorname{MEX}([1,2,3,4,5])=0$, and $\operatorname{MEX}([0,1,2,4,5])=3$.

Since the total number of such permutations can be very large, you will have to print its remainder modulo $10^9+7$.

In this problem, a permutation of size $n$ is an array consisting of $n$ distinct integers from $0$ to $n-1$ in arbitrary order. For example, $[1,0,2,4,3]$ is a permutation, while $[0,1,1]$ is not, since $1$ appears twice in the array. $[0,1,3]$ is also not a permutation, since $n=3$ and there is a $3$ in the array.


-----Input-----

Each test contains multiple test cases. The first line of input contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The following lines contain the descriptions of the test cases.

The first line of each test case contains a single integer $n$ ($1 \le n \le 10^5$) — the size of permutation $a$.

The second line of each test case contains $n$ distinct integers $a_1,a_2,\ldots,a_n$ ($0 \le a_i \lt n$) — the elements of permutation $a$.

It is guaranteed that the sum of $n$ across all test cases does not exceed $10^5$.


-----Output-----

For each test case, print a single integer, the number of permutations similar to permutation $a$, taken modulo $10^9+7$.


-----Examples-----

Input
5
5
4 0 3 2 1
1
0
4
0 1 2 3
6
1 2 4 0 5 3
8
1 3 7 2 5 0 6 4
Output
2
1
1
4
72


-----Note-----

For the first test case, the only permutations similar to $a=[4,0,3,2,1]$ are $[4,0,3,2,1]$ and $[4,0,2,3,1]$.

For the second and third test cases, the given permutations are only similar to themselves.

For the fourth test case, there are $4$ permutations similar to $a=[1,2,4,0,5,3]$:

$[1,2,4,0,5,3]$;

$[1,2,5,0,4,3]$;

$[1,4,2,0,5,3]$;

$[1,5,2,0,4,3]$.

Difficulty: MEDIUM_HARD
Tags: Combinatorics

Mathematics

Constructive algorithms

Starter code:

Solutions:
import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	m = 10 ** 9 + 7
	if n <= 2:
		return 1
	pos = [-1] * n
	for i in range(n):
		pos[arr[i]] = i
	(f, b) = (min(pos[0], pos[1]), max(pos[0], pos[1]))
	curr = b - f - 1
	ans = 1
	for i in range(2, n):
		if f < pos[i] < b:
			ans *= curr
			ans %= m
			curr -= 1
		elif pos[i] < f:
			curr += f - pos[i] - 1
			f = pos[i]
		else:
			curr += pos[i] - b - 1
			b = pos[i]
	return ans
for _ in range(int(input())):
	print(solve())


import sys
inputs = sys.stdin.readlines()
for i in range(2, len(inputs), 2):
	l = list(map(int, inputs[i].split()))
	if len(l) <= 1:
		sys.stdout.write('1\n')
		continue
	idx = [-1 for _ in range(len(l))]
	for i in range(len(l)):
		idx[l[i]] = i
	ans = [1 for _ in range(len(l))]
	left = min(idx[0], idx[1])
	right = max(idx[0], idx[1])
	for i in range(2, len(l)):
		if left < idx[i] < right:
			ans[i] = max(1, right - left - i + 1)
		elif idx[i] > right:
			right = idx[i]
		elif idx[i] < left:
			left = idx[i]
	answer = 1
	for a in ans:
		answer = answer * a % 1000000007
	sys.stdout.write(f'{answer}\n')


def main():
	MOD = 10 ** 9 + 7
	t = int(input())
	for _ in range(t):
		n = int(input())
		A = list(map(int, input().split()))
		dict = [0] * n
		ans = 1
		for i in range(n):
			dict[A[i]] = i
		minimum = n
		maximum = -1
		j = 0
		for i in range(n):
			update = False
			if minimum > dict[i]:
				update = True
				minimum = dict[i]
			if maximum < dict[i]:
				update = True
				maximum = dict[i]
			if not update:
				ans *= maximum + 1 - minimum - i
				ans %= MOD
				j += 1
		print(ans)
main()


import random
O = random.randint(10, 10 ** 7)

def main():
	N = int(input())
	for _ in range(N):
		n = int(input())
		arr = list(map(int, input().split()))
		ps = {}
		for (i, n) in enumerate(arr):
			ps[n] = i
		l = ps[0]
		r = ps[0]
		ans = 1
		for i in range(len(arr)):
			psi = ps[i]
			if l < psi < r:
				ans = ans * (r - l + 1 - i) % 1000000007
			else:
				l = min(l, psi)
				r = max(r, psi)
		print(ans)

def init():
	import os
	import sys
	sys.setrecursionlimit(2 * 10 ** 6)
	if 'CP_LOCAL_ENV' in os.environ:
		sys.stdin = open('cf_test_c.txt')
init()
main()


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	mod = 10 ** 9 + 7
	ans = 1
	p = [0] * n
	for i in range(n):
		p[a[i]] = i
	(l, r) = (p[0], p[0])
	for i in range(n):
		if p[i] < l:
			l = p[i]
		elif p[i] > r:
			r = p[i]
		else:
			ans = ans * (r - l + 1 - i) % mod
	print(ans)


import sys
LOCAL_DATA = 0
MULTI_CASE = 1
sys.setrecursionlimit(10000)
if LOCAL_DATA:
	sys.stdin = open('./dataset/in.txt', 'r')

def read_int():
	return int(input())

def read_list(t):
	return list(map(t, input().split()))

def run_test_case():
	n = read_int()
	a = read_list(int)
	if n == 1:
		print(1)
		return
	pos = [0] * n
	for i in range(n):
		pos[a[i]] = i
	mod = 10 ** 9 + 7
	ans = 1
	l = min(pos[0], pos[1])
	r = max(pos[0], pos[1])
	cnt = 2
	for i in range(2, n):
		if l < pos[i] < r:
			ans *= r - l + 1 - i
			ans %= mod
		else:
			l = min(l, pos[i])
			r = max(r, pos[i])
	print(ans)
case_count = 1
if MULTI_CASE:
	case_count = read_int()
for _ in range(case_count):
	run_test_case()


mod = 1000000000.0 + 7

def resi():
	n = int(input())
	a = list(map(int, input().split()))
	if n <= 2:
		print(1)
		return
	p = [0] * n
	for i in range(n):
		p[a[i]] = i
	(najmanji, najveci) = (min(p[0], p[1]), max(p[0], p[1]))
	res = 1
	for i in range(2, n):
		if p[i] < najmanji:
			najmanji = p[i]
		elif najveci < p[i]:
			najveci = p[i]
		else:
			res = res * (najveci - najmanji - (i - 1)) % mod
	print(int(res))
for i in range(int(input())):
	resi()


mod = 10 ** 9 + 7
t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	p = [0 for i in range(n)]
	for i in range(n):
		p[a[i]] = i
	left = right = p[0]
	ans = 1
	for i in range(n - 1):
		if p[i + 1] < left:
			left = p[i + 1]
		elif p[i + 1] > right:
			right = p[i + 1]
		else:
			ans = ans * (right - left - i) % mod
	print(ans % mod)


MOD = int(1000000000.0 + 7)
t = int(input())
for _ in range(t):
	_ = input()
	lst = [int(x) for x in input().split()]
	idx = [0] * len(lst)
	for i in range(len(lst)):
		idx[lst[i]] = i
	if len(lst) == 1:
		print(1)
	else:
		lhs = min(idx[0], idx[1])
		rhs = max(idx[1], idx[0])
		sm = 1
		for i in range(2, len(lst) - 1):
			if idx[i] < lhs:
				lhs = idx[i]
			elif idx[i] > rhs:
				rhs = idx[i]
			else:
				sm = sm * (rhs - lhs + 1 - i) % MOD
		print(sm)


t = int(input())
MOD = 10 ** 9 + 7
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	if n <= 2:
		print(1)
	else:
		b = {}
		for i in range(n):
			b[a[i]] = i
		r_min = min(b[0], b[1])
		r_max = max(b[0], b[1])
		tot = 1
		for i in range(2, n):
			if b[i] < r_min:
				r_min = b[i]
			elif b[i] > r_max:
				r_max = b[i]
			else:
				tot = tot * (r_max - r_min - i + 1) % MOD
		print(tot)


import sys, math
K = int(sys.stdin.readline().strip())
for _ in range(K):
	S = sys.stdin.readline().strip()
	S = int(S)
	l = list(map(int, sys.stdin.readline().strip().split()))
	d = {}
	for i in range(len(l)):
		d[l[i]] = i
	m1 = d[0]
	m2 = d[0]
	r = 1
	for i in range(1, len(l)):
		if m1 < d[i] < m2:
			r *= m2 - m1 - i + 1
			r = r % (10 ** 9 + 7)
		m1 = min(m1, d[i])
		m2 = max(m2, d[i])
	print(r)


mod = 10 ** 9 + 7
from collections import deque, defaultdict
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ind = defaultdict(int)
	for i in range(n):
		ind[l[i]] = i
	l = ind[0]
	r = ind[0]
	ans = 1
	for i in range(1, n):
		if ind[i] < l:
			l = ind[i]
			continue
		if ind[i] > r:
			r = ind[i]
			continue
		else:
			ans *= r - l + 1 - i
			ans %= mod
	print(ans)


t = int(input())
mod = int(1000000000.0) + 7
while t:
	t -= 1
	n = int(input())
	arr = [int(x) for x in input().split()]
	pos = [0] * n
	for i in range(len(arr)):
		pos[arr[i]] = i
	(l, r) = (pos[0], pos[0])
	ans = 1
	for i in range(1, n):
		if pos[i] < l:
			l = pos[i]
		elif pos[i] > r:
			r = pos[i]
		else:
			ans = ans * (r - l + 1 - i) % mod
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 1:
		print(1)
	else:
		d = dict()
		for i in range(n):
			d[a[i]] = i
		(left, right) = sorted([d[0], d[1]])
		total = right - left - 1
		ans = 1
		for i in range(2, n):
			if left < d[i] < right:
				ans = total * ans % 1000000007
				total -= 1
			elif d[i] < left:
				total += left - d[i] - 1
				left = d[i]
			elif d[i] > right:
				total += d[i] - right - 1
				right = d[i]
		print(ans % 1000000007)


dl = 1000000007
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = {}
	for i in range(n):
		b[a[i]] = i
	l = b[0]
	r = b[0] + 1
	mn = 0
	ans = 1
	while True:
		mn += 1
		while mn < n and l <= b[mn] < r:
			ans = ans * (r - l - mn) % dl
			mn += 1
		if mn == n:
			break
		if b[mn] >= r:
			r = b[mn] + 1
		else:
			l = b[mn]
	print(ans)


nn = int(input().strip())
for _ in range(nn):
	n = int(input().strip())
	arr = [int(x) for x in input().split(' ')]
	p = [0] * len(arr)
	for i in range(len(arr)):
		p[arr[i]] = i
	left = p[0]
	right = p[0]
	ans = 1
	for i in range(len(arr)):
		if p[i] < left:
			left = p[i]
		elif p[i] > right:
			right = p[i]
		else:
			ans *= right - left + 1 - i
			ans %= 1000000007
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	arr = [int(i) for i in input().split()]
	index = {arr[j]: j for j in range(n)}
	if n < 3:
		print(1)
	else:
		low = min(index[0], index[1])
		high = max(index[0], index[1])
		perm = 1
		for k in range(2, n):
			if index[k] < high and index[k] > low:
				perm = perm * (high - low + 1 - k) % 1000000007
			else:
				low = min(low, index[k])
				high = max(high, index[k])
		print(perm)


import math
p = 1000000007
t = int(input())
for _ in range(t):
	n = int(input())
	(*a,) = map(int, input().split())
	d = {}
	for i in range(n):
		d[a[i]] = i
	l = d[0]
	r = l
	ans = 1
	for i in range(1, n):
		v = d[i]
		if l < v < r:
			ans = ans * (r - l - i + 1) % p
		else:
			l = min(l, v)
			r = max(r, v)
	print(ans)


mod = 10 ** 9 + 7

def solve(arr, n):
	if n == 1 or n == 2:
		return 1
	d = dict()
	for i in range(n):
		d[arr[i]] = i
		if arr[i] == 0:
			temp1 = i
		if arr[i] == 1:
			temp2 = i
	if temp1 > temp2:
		(temp1, temp2) = (temp2, temp1)
	res = 1
	l = temp2 - temp1 + 1
	x = 2
	for i in range(2, n):
		if d[i] < temp1:
			x += 1
			temp1 = d[i]
		elif d[i] > temp2:
			x += 1
			temp2 = d[i]
		else:
			res = res * (l - x) % mod
			x += 1
		l = temp2 - temp1 + 1
	return res
t = int(input())
while t:
	n = int(input())
	arr = [int(i) for i in input().split()]
	print(solve(arr, n))
	t -= 1


def miis():
	return map(int, input().split())
mod = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	a = list(miis())
	pos = [0 for i in range(n)]
	for i in range(n):
		pos[a[i]] = i
	l = pos[0]
	r = pos[0]
	ans = 1
	for i in range(1, n):
		if pos[i] < l:
			l = pos[i]
		elif pos[i] > r:
			r = pos[i]
		else:
			ans *= r - l + 1 - i
			ans = ans % mod
	print(ans)


mod = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = [0] * n
	for i in range(n):
		b[a[i]] = i
	l = b[0]
	r = b[0]
	res = 1
	for i in range(1, n):
		if l < b[i] and b[i] < r:
			res = res * (r - l + 1 - i) % mod
		l = min(b[i], l)
		r = max(b[i], r)
	print(res)


t = int(input())
while t != 0:
	n = int(input())
	s = input().split()
	for i in range(len(s)):
		s[i] = int(s[i])
	index = dict()
	for i in range(len(s)):
		index[s[i]] = i
	if len(s) == 1:
		print(1)
	else:
		left = min(index[0], index[1])
		right = max(index[0], index[1])
		result = 1
		mod = 10 ** 9 + 7
		for i in range(2, len(s)):
			ref = index[i]
			if left < ref and ref < right:
				result = result * (right - left + 1 - i)
				result = result % mod
			elif ref <= left:
				left = ref
			else:
				right = ref
		print(result)
	t = t - 1


for i in range(int(input())):
	n = int(input())
	ind = [0] * n + [0]
	a = [*map(int, input().split())]
	for i in range(n):
		ind[a[i]] = i
	ans = 1
	(l, r) = sorted([ind[0], ind[1]])
	for i in range(2, n):
		if ind[i] > l and ind[i] < r:
			ans = ans * (r - l + 1 - i) % int(1000000000.0 + 7)
		r = max(r, ind[i])
		l = min(l, ind[i])
	print(ans)


M = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	a = (*map(int, input().split()),)
	b = [0] * n
	for i in range(n):
		b[a[i]] = i
	cnt = 1
	l = r = b[0]
	for i in range(1, n):
		p = b[i]
		if l < p < r:
			cnt = cnt * (r - l + 1 - i) % M
		l = min(l, p)
		r = max(r, p)
	print(cnt)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ans = 1
	t = [0 for _ in range(n)]
	for i in range(n):
		t[l[i]] = i
	a = t[0]
	b = a
	i = 1
	for i in range(1, n):
		if t[i] < a or t[i] > b:
			(a, b) = (min(a, t[i]), max(b, t[i]))
		else:
			ans = (b - a - i + 1) * ans % 1000000007
	print(ans)


MOD = 10 ** 9 + 7
mem = [1]

def fac(n):
	while len(mem) < n + 1:
		mem.append(mem[-1] * len(mem) % MOD)
	return mem[n]
for case in range(int(input())):
	n = int(input())
	a = [int(j) for j in input().split()]
	loc = [0] * n
	for i in range(n):
		loc[a[i]] = i
	num = 1
	denom = 1
	moves = 1
	s = e = loc[0]
	p = []
	for i in range(1, n):
		idx = loc[i]
		if idx < s:
			s = idx
			moves += 1
		elif idx > e:
			e = idx
			moves += 1
		else:
			p.append(e - s - moves + 1)
	d = {}
	for i in p:
		d[i] = d.get(i, 0) + 1
	used = 0
	for i in sorted(d.keys()):
		spaces = i - used
		num = num * fac(spaces) % MOD
		denom = denom * fac(spaces - d[i]) % MOD
		used += d[i]
	print(num * pow(denom, MOD - 2, MOD) % MOD)


for s in [*open(0)][2::2]:
	n = len((a := s.split()))
	i = j = r = 0
	k = 1
	for (i, j) in sorted(zip(map(int, a), range(n))):
		k = k * (j < n or j > r or r - n - i + 1) % (10 ** 9 + 7)
		n = min(n, j)
		r = max(r, j)
	print(k)


dl = 1000000007
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = [0 for _ in range(n)]
	for i in range(n):
		b[a[i]] = i
	l = b[0]
	r = b[0] + 1
	mn = 0
	pr = 0
	ans = 1
	cnt = 1
	while l > 0 or r < n:
		while mn < n and l <= b[mn] < r:
			mn += 1
		for i in range(mn - pr - 1):
			ans = (r - l - cnt - i) * ans % dl
		cnt += mn - pr
		if b[mn] >= r:
			r = b[mn] + 1
		else:
			l = b[mn]
		pr = mn
	for i in range(2, n - cnt + 1):
		ans = i * ans % dl
	print(ans)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l1 = [0] * n
	for i in range(n):
		l1[l[i]] = i
	if n == 1:
		print(1)
	else:
		x = min(l1[0], l1[1])
		y = max(l1[0], l1[1])
		ans = 1
		for i in range(2, n):
			x = min(l1[i - 1], x)
			y = max(l1[i - 1], y)
			z = l1[i]
			if (x - z) * (y - z) < 0:
				ans *= y - x - i + 1
			ans %= 10 ** 9 + 7
		print(ans)