MEX 的下取整（困难版）AI (CI翻译)
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.
这是本题的困难版本。两个版本的区别在于，本版本要求统计满足约束条件的集合数量。只有解决了本题的所有版本，你才能进行 hack。AI (CI翻译)
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{∗}}$
定义 $$ f(S,x)=\text{mex}\left(\left\{\left\lfloor \frac{y}{x}\right\rfloor : y\in S\right\}\right), $$ 其中，$S$ 是一个非负整数集合，$x$ 是一个正整数。$^{\text{∗}}$AI (CI翻译)
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$.
Farmer John 选择一个（可以为空的）子集 $A\subseteq \{0,1,\ldots,n-1\}$。随后，他构造一个长度为 $n$ 的数组 $a$，其中对于每个 $1\le k\le n$，都有 $a_k = f(A,k)$。AI (CI翻译)
Bessie, being a mischievous cow, hides the set $A$. Farmer John is left only with the array $a_1,a_2,\ldots,a_n$.
Bessie 是一头调皮的奶牛，她把集合 $A$ 藏了起来。Farmer John 手中只剩下数组 $a_1,a_2,\ldots,a_n$。AI (CI翻译)
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.
你的任务是统计有多少个集合（包括空集）$B \subseteq \{0,1,\ldots,n-1\}$，满足对于每个 $1 \le k \le n$，都有 $f(B,k)=a_k$。由于答案可能非常大，请输出答案对 $10^9+7$ 取模的结果。Farmer John 只会给出存在这样的 $B$ 的数组。AI (CI翻译)
$^{\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)
$^{\text{∗}}$$\operatorname{mex}(c)$ 表示集合 $c$ 的最小排除数（MEX）$^{\text{∗}}$。（在本题中，即未出现在集合中的最小非负整数）AI (CI翻译)
Input
输入格式
AI (CI翻译)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.
每个输入包含多组测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。接下来是各组测试用例的描述。AI (CI翻译)
The first line of each test case contains a single integer $n$ ($1 \leq n \leq 10^5$).
每组测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 10^5$）。AI (CI翻译)
The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($0 \leq a_i \leq n$).
第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$0 \leq a_i \leq n$）。AI (CI翻译)
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$.
给出的数组保证存在 $B \subseteq \{0,1,\ldots,n-1\}$，使得对于每个 $1 \le k \le n$，都有 $f(B,k)=a_k$。AI (CI翻译)
It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.
保证所有测试用例的 $n$ 之和不超过 $10^5$。AI (CI翻译)
Output
输出格式
AI (CI翻译)For each testcase, output one number, the number of sets $B$ that satisfy the constraints modulo $10^9 + 7$.
对于每组测试用例，输出一个数，表示满足约束条件的集合 $B$ 的数量对 $10^9 + 7$ 取模的结果。AI (CI翻译)
Note
说明
AI (CI翻译)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\}.$$$$
对于第一组测试用例，这 $6$ 个子集为 $$\{1, 2, 5\}, \{1, 3, 5\}, \{1, 2, 3, 5\}, \{1, 2, 4, 5\}, \{1, 3, 4, 5\}, \{1, 2, 3, 4, 5\}.$$$$AI (CI翻译)
For the second testcase, the only subset that satisfies $f(B,k) = a_k$ for every $1 \le k \le n$ is $\{0, 1\}$$$.
对于第二组测试用例，唯一满足对于每个 $1 \le k \le n$ 都有 $f(B,k) = a_k$ 的子集是 $\{0, 1\}$$$。AI (CI翻译)
样例
3
6
0 3 2 2 2 1
5
2 1 1 1 1
6
1 2 1 1 1 1
6
1
1
题面与样例版权归 Codeforces 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。