CF2234E.Vlad, Misha and Two Arrays

Vlad thought of a permutation $p$ of length $n$. After that, for each $i$ from $1$ to $n$, he counted the number of pairs $l, r$ such that $1 \leq l \leq r \leq n$ and the minimum number among $p_l, p_{l+1}, \ldots, p_r$ is equal to $p_i$, and wrote this number into $a_i$.

Now he gave Misha the numbers $a_1, a_2, \ldots, a_n$ and asked him to guess the permutation $p$. However, Misha quickly realized that it is not always possible to uniquely restore the permutation $p$. Therefore, he decided to surprise Vlad and tell him the number of suitable permutations $p$ modulo $10^9+7$. Help him with this. Note that Vlad could have made a mistake, and there may be no such permutations.

弗拉德构思了一个长度为 $n$ 的排列 $p$。之后，对于每个从 $1$ 到 $n$ 的 $i$，他统计了满足 $1 \leq l \leq r \leq n$ 且子数组 $p_l, p_{l+1}, \ldots, p_r$ 中最小值恰好等于 $p_i$ 的区间对 $(l, r)$ 的数量，并将该数量记为 $a_i$。

现在他将数组 $a_1, a_2, \ldots, a_n$ 告诉了米沙，让他据此猜出原排列 $p$。然而，米沙很快意识到，原排列 $p$ 并不总是能被唯一确定。因此，他决定给弗拉德一个惊喜，告诉他自己算出的满足条件的排列 $p$ 的个数（对 $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.

In the first line of each test case, a natural number $n$ ($1 \leq n \leq 5 \cdot 10^5$) is given — the size of the permutation.

In the second line of each test case, $n$ numbers $a_1, a_2, \ldots a_n$ ($1 \leq a_i \leq 10^{12}$) are given — the array $a$ that Vlad gave to Misha.

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

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

在每个测试用例的第一行中，给出一个自然数 $n$（$1 \leq n \leq 5 \cdot 10^5$）—— 即排列的大小。

在每个测试用例的第二行中，给出 $n$ 个数 $a_1, a_2, \ldots a_n$（$1 \leq a_i \leq 10^{12}$）—— 即 Vlad 给 Misha 的数组 $a$。

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

For each test case, output the number of suitable permutations modulo $10^9+7$.

对于每个测试用例，输出满足条件的排列数量对 $10^9+7$ 取模的结果。

In the first test case, there exist exactly two suitable permutations: $p = [2, 1, 3]$ and $p = [3, 1, 2]$.

In the second test case, the only suitable permutation is $p = [4, 3, 2, 1]$.

In the fourth test case, it can be shown that no permutation $p$ corresponds to the array $a$.

在第一个测试用例中，恰好存在两个合适的排列：$p = [2, 1, 3]$ 和 $p = [3, 1, 2]$。

在第二个测试用例中，唯一的合适排列是 $p = [4, 3, 2, 1]$。

在第四个测试用例中，可以证明不存在任何排列 $p$ 与数组 $a$ 对应。