A2. Floor of MEX (Hard Version)
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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)

Input

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$$$.

Output

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

Example
Input
3
6
0 3 2 2 2 1
5
2 1 1 1 1
6
1 2 1 1 1 1
Output
6
1
1
Note

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\}$$$.