E. Влад, Миша, два массива
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Влад загадал перестановку $$$p$$$ длины $$$n$$$. После этого для каждого $$$i$$$ от $$$1$$$ до $$$n$$$ он посчитал количество пар таких $$$l, r$$$, что $$$1 \leq l \leq r \leq n$$$ и минимальное число среди $$$p_l, p_{l+1}, \ldots, p_r$$$ равно $$$p_i$$$, и записал это число в $$$a_i$$$.

Теперь он дал Мише числа $$$a_1, a_2, \ldots, a_n$$$ и сказал ему отгадать перестановку $$$p$$$. Однако Миша быстро понял, что однозначно восстановить перестановку $$$p$$$ не всегда получится. Поэтому он решил удивить Влада и сказать ему количество подходящих перестановок $$$p$$$ по модулю $$$10^9+7$$$. Помогите ему в этом. Учтите, что Влад мог ошибиться, и таких перестановок может не быть.

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

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

В первой строке каждого набора входных данных дано натуральное число $$$n$$$ ($$$1 \leq n \leq 5 \cdot 10^5$$$) — размер перестановки.

Во второй строке каждого набора входных данных дано $$$n$$$ чисел $$$a_1, a_2, \ldots a_n$$$ ($$$1 \leq a_i \leq 10^{12}$$$) — массив $$$a$$$, который Влад дал Мише.

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

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

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

Пример
Входные данные
4
3
1 4 1
4
1 2 3 4
4
1 6 1 2
3
3 3 3
Выходные данные
2
1
3
0
Примечание

В первом наборе входных данных существует ровно две подходящие перестановки: $$$p = [2, 1, 3]$$$ и $$$p = [3, 1, 2]$$$.

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

В четвёртом наборе входных данных можно показать, что ни одна перестановка $$$p$$$ не соответствует массиву $$$a$$$.