C. Третья задача
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана перестановка $$$a_1,a_2,\ldots,a_n$$$ чисел от $$$0$$$ до $$$n - 1$$$. Вам нужно посчитать количество перестановок $$$b_1,b_2,\ldots,b_n$$$, похожих на перестановку $$$a$$$.

Две перестановки $$$a$$$ и $$$b$$$ размера $$$n$$$ называются похожими, если для всех отрезков $$$[l,r]$$$ ($$$1 \le l \le r \le n$$$) выполняется следующее условие: $$$$$$\operatorname{MEX}([a_l,a_{l+1},\ldots,a_r])=\operatorname{MEX}([b_l,b_{l+1},\ldots,b_r]),$$$$$$ где $$$\operatorname{MEX}$$$ набора чисел $$$c_1,c_2,\ldots,c_k$$$ определяется как наименьшее неотрицательное целое число $$$x$$$, которое не встречается в наборе чисел $$$c$$$. Например, $$$\operatorname{MEX}([1,2,3,4,5])=0$$$, а $$$\operatorname{MEX}([0,1,2,4,5])=3$$$.

Так как количество таких перестановок может быть очень большим, вам нужно вывести его остаток по модулю $$$10^9+7$$$.

В этой задаче перестановкой размера $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$0$$$ до $$$n-1$$$ в произвольном порядке. Например, $$$[1,0,2,4,3]$$$ является перестановкой, а $$$[0,1,1]$$$ не является, так как $$$1$$$ встречается в массиве дважды. $$$[0,1,3]$$$ также не является перестановкой, так как $$$n=3$$$ и в массиве есть число $$$3$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится единственное целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит единственное целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — размер перестановки $$$a$$$.

Вторая строка каждого набора входных данных содержит $$$n$$$ различных целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$0 \le a_i \lt n$$$) — элементы перестановки $$$a$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

Выходные данные

Для каждого набора входных данных выведите единственное целое число — количество перестановок, похожих на перестановку $$$a$$$, взятое по модулю $$$10^9+7$$$.

Пример
Входные данные
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
Выходные данные
2
1
1
4
72
Примечание

В первом наборе входных данных единственными перестановками, похожими на $$$a=[4,0,3,2,1]$$$, являются $$$[4,0,3,2,1]$$$ и $$$[4,0,2,3,1]$$$.

Во втором и третьем наборах входных данных только данные перестановки похожи на себя.

В четвёртом наборе входных данных есть $$$4$$$ перестановки, похожие на $$$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]$$$.