A2. Округление MEX вниз (сложная версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Отличие между версиями заключается в том, что в этой версии вам нужно подсчитать количество множеств, удовлетворяющих ограничениям. Вы можете делать взломы только в том случае, если решили все версии этой задачи.

Пусть $$$$$$ f(S,x)=\text{mex}\left(\left\{\left\lfloor \frac{y}{x}\right\rfloor : y\in S\right\}\right), $$$$$$ где $$$S$$$ — множество неотрицательных целых чисел, а $$$x$$$ — положительное целое число. $$$^{\text{∗}}$$$

Фермер Джон выбирает некоторое (возможно, пустое) подмножество $$$A\subseteq \{0,1,\ldots,n-1\}$$$. Затем он строит массив $$$a$$$ длины $$$n$$$, где $$$a_k = f(A,k)$$$ для каждого $$$1\le k\le n$$$.

Озорная корова Бесси прячет множество $$$A$$$. У Фермера Джона остаётся только массив $$$a_1,a_2,\ldots,a_n$$$.

Ваша задача — подсчитать количество множеств (включая пустое) $$$B \subseteq \{0,1,\ldots,n-1\}$$$ таких, что $$$f(B,k)=a_k$$$ для каждого $$$1 \le k \le n$$$. Поскольку это количество может быть очень большим, выведите его по модулю $$$10^9+7$$$. Фермер Джон будет давать только такие массивы, для которых подобное $$$B$$$ существует.

$$$^{\text{∗}}$$$$$$\operatorname{mex}(c)$$$ обозначает наименьшее исключенное (MEX)$$$^{\text{∗}}$$$ набора чисел $$$c$$$. (в данном случае это минимальное неотрицательное целое число, отсутствующее во множестве)

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

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

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

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

Вам будут даны только такие массивы, для которых существует такое подмножество $$$B \subseteq \{0,1,\ldots,n-1\}$$$, что $$$f(B,k)=a_k$$$ для каждого $$$1 \le k \le n$$$.

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

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

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

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

В первом наборе входных данных существует $$$6$$$ подмножеств: $$$$$$\{1, 2, 5\}, \{1, 3, 5\}, \{1, 2, 3, 5\}, \{1, 2, 4, 5\}, \{1, 3, 4, 5\}, \{1, 2, 3, 4, 5\}.$$$$$$

Во втором наборе входных данных единственным подмножеством, для которого $$$f(B,k) = a_k$$$ выполняется для каждого $$$1 \le k \le n$$$, является $$$\{0, 1\}$$$.