CF2262C Traveling the World

有 $n$ 个岛屿，编号从 $1$ 到 $n$。第 $i$ 个岛屿的数值为 $a_i$。这些数值 $a_1,a_2,\ldots,a_n$ 严格递增，且 $a_1=0$。 Farmer John 想要重新排列这些岛屿。经过重新排列后，它们的数值构成数组 $b_1,b_2,\ldots,b_n$，它是 $a$ 的一个排列。 Bessie 按照如下规则在岛屿之间旅行：假设她目前在重新排列后的位置 $i$ 的岛屿上。那么如果 $ b_i + b_j = \max(b_i,b_{i+1},\ldots,b_n) $ 则 Bessie 可以从第 $i$ 个位置的岛屿前往第 $j$ 个位置的岛屿。 一个排列 $b$ 被称为“优良的”，如果存在一系列不同的位置 $p_1,p_2,\ldots,p_n$，使得对于每个 $1\le i < n$，Bessie 能够从 $p_i$ 旅行至 $p_{i+1}$。换句话说，Bessie 能按照题目中的规则恰好遍历所有位置（也即所有岛屿）一次。 请统计岛屿的“优良排列”数目。由于答案可能很大，请输出对 $10^9+7$ 取模的结果。

每个测试点包含多组测试用例。第一行为测试用例数量 $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 < a_2 < \cdots < a_n$。 保证所有测试用例中 $n$ 的总和不超过 $2\cdot 10^5$。

对于每组测试用例，输出一个整数，表示岛屿的“优良排列” $b$ 的个数，对 $10^9+7$ 取模。

对于第一个测试用例，有一种满足条件的 $b$ 为 $[2,1,0,5,3,4]$。 注意，Bessie 可以从 $1 \to 5$，因为 $2 + 3 = b_1 + b_5 = \max(b_1,b_2,\ldots,b_6) = 5$。 同理，Bessie 可以从 $5 \to 2$，$2 \to 6$，$6 \to 3$，$3 \to 4$。 因此，从岛屿 $1$ 出发，Bessie 可以按路径 $1\to 5\to 2\to 6\to 3\to 4$ 依次遍历所有岛屿，所以该排列是优良的。 对于第二个测试用例，可以证明没有优良排列。因此，答案为 $0$。 由 ChatGPT 5 翻译