CF2262A2.Floor of MEX (Hard Version)

This is the hard version of the problem. The difference between the versions is that in this version, you need to count how many sets satisfy the constraints. You can hack only if you solved all versions of this problem.

Let $$ f(S,x)=\text{mex}\left(\left\{\left\lfloor \frac{y}{x}\right\rfloor : y\in S\right\}\right), $$ where $S$ is a set of non-negative integers and $x$ is a positive integer. $^{\text{∗}}$

Farmer John chooses a (possibly empty) subset $A\subseteq {0,1,\ldots,n-1}$. He then constructs an array $a$ of length $n$, where $a_k = f(A,k)$ for every $1\le k\le n$.

Bessie, being a mischievous cow, hides the set $A$. Farmer John is left only with the array $a_1,a_2,\ldots,a_n$.

Your task is to count how many sets (including the empty set) $B \subseteq {0,1,\ldots,n-1}$ such that $f(B,k)=a_k$ for every $1 \le k \le n$. Since the number can be very large, output it modulo $10^9+7$. Farmer John will only give you arrays where such a $B$ exists.

$^{\text{∗}}$$\operatorname{mex}(c)$ denotes the minimum excluded (MEX)$^{\text{∗}}$ of the collection $c$. (in this case, the minimum non-negative integer not present in the set)

这是该问题的困难版本。两个版本的区别在于：在此版本中，你需要计算满足约束条件的集合数量。仅当你解决了该问题的所有版本后，你才可以进行 hack。

定义

$$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\}$。然后他构造一个长度为 $n$ 的数组 $a$，使得对每个 $1\le k\le n$，均有 $a_k = f(A,k)$。

调皮的奶牛贝茜隐藏了集合 $A$。农夫约翰手中仅剩下数组 $a_1,a_2,\ldots,a_n$。

你的任务是：计算满足对每个 $1 \le k \le n$ 均有 $f(B,k)=a_k$ 的集合（包括空集）$B \subseteq \{0,1,\ldots,n-1\}$ 的个数。由于答案可能非常大，请输出其对 $10^9+7$ 取模的结果。农夫约翰只会给你那些确实存在满足条件的 $B$ 的数组。

$^{\text{∗}}$$\operatorname{mex}(c)$ 表示集合 $c$ 的最小未出现值（MEX）$^{\text{∗}}$（即不在该集合中的最小非负整数）。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \leq n \leq 10^5$).

The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($0 \leq a_i \leq n$).

You will only be given arrays where there exists $B \subseteq {0,1,\ldots,n-1}$ such that $f(B,k)=a_k$ for every $1 \le k \le n$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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\}$，使得对每个 $1 \le k \le n$ 都有 $f(B,k)=a_k$。

保证所有测试用例的 $n$ 之和不超过 $10^5$。

For each testcase, output one number, the number of sets $B$ that satisfy the constraints modulo $10^9 + 7$.

对于每个测试用例，输出一个数字，即满足约束条件的集合 $B$ 的数量对 $10^9 + 7$ 取模的结果。

For the first testcase, the $6$ subsets are $$\{1, 2, 5\}, \{1, 3, 5\}, \{1, 2, 3, 5\}, \{1, 2, 4, 5\}, \{1, 3, 4, 5\}, \{1, 2, 3, 4, 5\}.$$

For the second testcase, the only subset that satisfies $f(B,k) = a_k$ for every $1 \le k \le n$ is ${0, 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\}.$$

对于第二个测试用例，唯一满足对每个 $1 \le k \le n$ 都有 $f(B,k) = a_k$ 的子集是 $\{0, 1\}$。