E2. N-MEX (Версия для подсчета)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Атака на базу строителя (Этап 2) — Supercell, Clash of Clans

Это counting версия задачи. Отличие между версиями заключается в том, что в этой версии вам нужно подсчитать количество массивов, где $$$0 \leq b_i \leq n$$$. Вы можете делать взломы только в том случае, если решили все версии этой задачи.

Мастер-строитель не любит повторяющиеся задачи — ремонт базы, улучшение ратуши пятнадцать раз и решение еще большего количества задач по MEX. Поэтому это не будет вашей обычной задачей по MEX.

Для любого положительного целого числа $$$k$$$ определите $$$k$$$-mex коллекции целых чисел $$$S$$$ как $$$k$$$-е по величине неотрицательное целое число, отсутствующее в $$$S$$$. Например, $$$1$$$-mex и $$$2$$$-mex для $$$[1, 2, 1]$$$ равны $$$0$$$ и $$$3$$$ соответственно.

Пусть $$$n$$$ будет положительным целым числом, и рассмотрим массив неотрицательных целых чисел $$$[a_1, \ldots, a_n]$$$. Вычислите количество массивов неотрицательных целых чисел $$$[b_1, \ldots, b_n]$$$, таких что:

  • Для всех $$$1 \leq i \leq n$$$, $$$(n-i+1)$$$-mex массива $$$[b_1, \ldots, b_i]$$$ равен $$$a_i$$$.
  • Кроме того, для всех $$$1 \leq i \leq n$$$, $$$0 \leq b_i \leq n$$$.
Поскольку количество таких массивов может быть большим, выведите ответ по модулю $$$10^9 + 7$$$.
Входные данные

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

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

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

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

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

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

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

В первом наборе массив $$$a = [3, 3, 1]$$$. Существует ровно шесть таких массивов $$$b$$$, которые подходят. Один из таких примеров — массив $$$b = [2, 0, 2]$$$, который удовлетворяет условиям, потому что:

  • $$$3$$$-mex массива $$$[b_1] = [2]$$$ равен $$$a_1 = 3$$$,
  • $$$2$$$-mex массива $$$[b_1, b_2] = [2, 0]$$$ равен $$$a_2 = 3$$$,
  • $$$1$$$-mex массива $$$[b_1, b_2, b_3] = [2, 0, 2]$$$ равен $$$a_3 = 1$$$.

Во втором наборе массив $$$a = [2, 1, 3]$$$. Можно показать, что подходящего массива $$$b$$$ не существует.