← 返回题目列表

Codeforces · 2234/E

E. 弗拉德、米莎和两个阵列

中文机器翻译题面 查看原题

Vlad 想到了长度为 $$$n$$$ 的排列 $$$p$$$。之后,对于从$$$1$$$到$$$n$$$的每个$$$i$$$,他计算了$$$l、r$$$对的数量,使得$$$1 \leq l \leq r \leq n$$$以及$$$p_l、p_{l+1}、\ldots、p_r$$$中的最小数等于$$$p_i$$$,并将这个数字写入$$$a_i$$$。

现在他给 Misha 数字 $$$a_1, a_2, \ldots, a_n$$$ 并要求他猜测排列 $$$p$$$。然而,Misha 很快意识到,并不总是能够唯一地恢复排列 $$$p$$$。因此,他决定给Vlad一个惊喜,并告诉他$$$p$$$模$$$10^9+7$$$的合适排列数。帮助他解决这个问题。请注意,弗拉德可能犯了一个错误,并且可能不存在这样的排列。

输入

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

在第四个测试用例中,可以证明没有排列$$$p$$$对应于数组$$$a$$$。