题目描述

Vlad 想了一个长度为 $n$ 的排列 $p$。之后，对于每个 $i$（从 $1$ 到 $n$），他统计了满足 $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$ 给了 Misha，让他猜排列 $p$。然而 Misha 很快发现，排列 $p$ 并不总是能被唯一还原。因此他决定给 Vlad 一个惊喜，告诉他满足条件的排列 $p$ 的数量对 $10^9+7$ 取模的结果。请帮助他完成这件事。注意 Vlad 可能算错了，即可能不存在这样的排列。

输入格式

每个测试包含多个测试数据。第一行包含测试数据的数量 $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$。

输出格式

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

4
3
1 4 1
4
1 2 3 4
4
1 6 1 2
3
3 3 3

2
1
3
0

提示

在第一个测试数据中，恰好存在两个满足条件的排列：$p = [2, 1, 3]$ 和 $p = [3, 1, 2]$。

在第二个测试数据中，唯一满足条件的排列是 $p = [4, 3, 2, 1]$。

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