C. Путешествие по миру
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Есть $$$n$$$ островов, пронумерованных от $$$1$$$ до $$$n$$$. Значение $$$i$$$-го острова равно $$$a_i$$$. Значения $$$a_1,a_2,\ldots,a_n$$$ строго возрастают, причём $$$a_1=0$$$.

Фермер Джон хочет переставить острова. После перестановки их значения образуют массив $$$b_1,b_2,\ldots,b_n$$$, являющийся перестановкой массива $$$a$$$.

Затем Бесси перемещается между островами по следующему правилу. Предположим, что после перестановки она находится на острове в позиции $$$i$$$. Тогда Бесси может переместиться с острова в позиции $$$i$$$ на остров в позиции $$$j$$$, если $$$$$$ b_i + b_j = \max(b_i,b_{i+1},\ldots,b_n). $$$$$$

Перестановка $$$b$$$ называется хорошей, если существует последовательность различных позиций $$$p_1,p_2,\ldots,p_n$$$ такая, что Бесси может переместиться из $$$p_i$$$ в $$$p_{i+1}$$$ для каждого $$$1\le i \lt n$$$. Иными словами, Бесси может посетить все позиции (а следовательно, и все острова) ровно по одному разу, совершая только допустимые перемещения.

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

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

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

В первой строке каждого набора входных данных содержится одно целое число $$$n$$$ ($$$4 \le n \le 2 \cdot 10^5$$$).

Во второй строке каждого набора входных данных содержатся $$$n$$$ различных целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$0\le a_i\le 10^9$$$).

Гарантируется, что $$$a_1=0$$$ и $$$a_1 \lt a_2 \lt \cdots \lt a_n$$$.

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

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

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

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

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

Заметим, что Бесси может переместиться из $$$1 \to 5$$$, поскольку $$$2 + 3 = b_1 + b_5 = \max(b_1,b_2,\ldots,b_6) = 5$$$.

Аналогично, Бесси может переместиться из $$$5 \to 2$$$, $$$2\to 6$$$, $$$6\to 3$$$, $$$3\to 4$$$.

Таким образом, начав с острова $$$1$$$, Бесси может пройти по пути $$$1\to 5\to 2\to 6\to 3\to 4$$$, посещающему каждый остров. Следовательно, эта перестановка является хорошей.

Для второго набора входных данных можно показать, что хороших перестановок не существует. Поэтому ответ равен $$$0$$$.