CF2262A2 Floor of MEX (Hard Version)

**这是该问题的困难版本。不同之处在于，在本版本中你需要统计有多少个集合满足约束条件。只有在你解决了所有版本的问题后，才可以进行 hack。** 定义 $$ f(S, x) = \operatorname{mex}\left(\left\{\left\lfloor \frac{y}{x} \right\rfloor : y \in S \right\}\right), $$ 其中 $S$ 是一个非负整数集合，$x$ 是一个正整数。$^{\text{∗}}$ Farmer John 从 $A \subseteq \{0, 1, \ldots, n-1\}$（可以为空）中选择一个子集。然后，他构造一个长度为 $n$ 的数组 $a$，其中 $a_k = f(A, k)$，$1 \le k \le n$。 Bessie，这头调皮的牛，把集合 $A$ 藏起来了。Farmer John 只剩下数组 $a_1, a_2, \ldots, a_n$。 你的任务是统计有多少个集合（包括空集）$B \subseteq \{0, 1, \ldots, n-1\}$，使得对于每个 $1 \le k \le n$，都有 $f(B, k) = a_k$。由于答案可能非常大，请输出对 $10^9+7$ 取模后的结果。**Farmer John 只会给你至少存在一个 $B$ 满足条件的数组。** $^{\text{∗}} \operatorname{mex}(c)$ 表示集合 $c$ 的最小未出现非负整数（MEX）。在本题中，这是集合 $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$ 取模。

对于第一个测试用例，$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 \leq k \leq n$ 的子集是 $\{0, 1\}$。 由 ChatGPT 5 翻译