CF2262C.Traveling the World

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

有 $n$ 座岛屿，编号从 $1$ 到 $n$。第 $i$ 座岛屿的权值为 $a_i$。权值序列 $a_1,a_2,\ldots,a_n$ 严格递增，且 $a_1=0$。

农夫约翰希望重新排列这些岛屿。重排后，它们的权值构成数组 $b_1,b_2,\ldots,b_n$，即 $a$ 的一个排列。

随后，奶牛贝茜按照如下规则在岛屿间移动：假设她当前位于重排后位置 $i$ 的岛屿上，则贝茜可以从位置 $i$ 的岛屿移动到位置 $j$ 的岛屿，当且仅当

$$b\_i + b\_j = \max(b\_i,b\_{i+1},\ldots,b\_n).$$

若存在一个由互不相同的位置 $p_1,p_2,\ldots,p_n$ 构成的序列，使得对每个 $1\le i < n$，贝茜均可从位置 $p_i$ 移动到位置 $p_{i+1}$，则称该重排 $b$ 是好的。换言之，贝茜能恰好访问每个位置（从而访问每座岛屿）一次，且每次移动均满足上述规则。

请计算岛屿的好重排数量。由于答案可能很大，请输出其对 $10^9+7$ 取模的结果。

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

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$4 \le n \le 2 \cdot 10^5$）。

每个测试用例的第二行包含 $n$ 个互不相同的整数 $a_1,a_2,\ldots,a_n$（$0\le a_i\le 10^9$）。

保证 $a_1=0$，且 $a_1 \lt a_2 \lt \cdots \lt a_n$。

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

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

对于每个测试用例，输出一个整数——数组 $a$ 的“好”重排 $b$ 的数量，对 $10^9+7$ 取模。

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

对于第一个测试用例，一个可行的 $b$ 是 $[2,1,0,5,3,4]$。

注意，贝茜可以从岛屿 $1$ 到达岛屿 $5$，因为 $2 + 3 = b_1 + b_5 = \max(b_1,b_2,\ldots,b_6) = 5$。

类似地，贝茜还可以从 $5 \to 2$、$2\to 6$、$6\to 3$、$3\to 4$。

因此，从岛屿 $1$ 出发，贝茜可以沿路径 $1\to 5\to 2\to 6\to 3\to 4$ 行进，从而访问所有岛屿。故该重排是“好的”。

对于第二个测试用例，可以证明不存在任何“好的”重排。因此答案为 $0$。