C. Traveling the World
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ islands, numbered from $$$1$$$ to $$$n$$$. The $$$i$$$-th island has value $$$a_i$$$. The values $$$a_1,a_2,\ldots,a_n$$$ are strictly increasing, and $$$a_1=0$$$.

Farmer John wants to rearrange the islands. After rearranging them, their values form an array $$$b_1,b_2,\ldots,b_n$$$, which is a rearrangement of $$$a$$$.

Bessie then travels between islands according to the following rule. Suppose she is currently on the island in position $$$i$$$ after the rearrangement. Then Bessie may travel from the island in position $$$i$$$ to the island in position $$$j$$$ if $$$$$$ b_i + b_j = \max(b_i,b_{i+1},\ldots,b_n). $$$$$$

A rearrangement $$$b$$$ is called good if there exists a sequence of distinct positions $$$p_1,p_2,\ldots,p_n$$$ such that Bessie can travel from $$$p_i$$$ to $$$p_{i+1}$$$ for every $$$1\le i \lt n$$$. In other words, Bessie can visit all positions (and therefore all islands) exactly once by following valid travels.

Count the number of good rearrangements of the islands. Since the number can be large, output it modulo $$$10^9+7$$$.

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 $$$n$$$ ($$$4 \le n \le 2 \cdot 10^5$$$).

The second line of each test case contains $$$n$$$ distinct integers $$$a_1,a_2,\ldots,a_n$$$ ($$$0\le a_i\le 10^9$$$).

It is guaranteed that $$$a_1=0$$$ and $$$a_1 \lt a_2 \lt \cdots \lt a_n$$$.

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

Output

For each test case, output a single integer — the number of good rearrangements $$$b$$$ of $$$a$$$, modulo $$$10^9+7$$$.

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

For the first testcase, one $$$b$$$ that works is $$$[2,1,0,5,3,4]$$$.

Note that Bessie can travel from $$$1 \to 5$$$ since $$$2 + 3 = b_1 + b_5 = \max(b_1,b_2,\ldots,b_6) = 5$$$.

Similarly, Bessie can travel from $$$5 \to 2$$$, $$$2\to 6$$$, $$$6\to 3$$$, $$$3\to 4$$$.

Thus, starting from island $$$1$$$, Bessie can follow the path $$$1\to 5\to 2\to 6\to 3\to 4$$$ which visits every island. Therefore, this rearrangement is good.

For the second testcase, it can be shown that there are no good rearrangements. Therefore, the answer is $$$0$$$.