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$$$ 为模的合适排列数。
示例
输入复制
431 4 141 2 3 441 6 1 233 3 3
输出复制
2130
注意
在第一个测试用例中,恰好存在两个合适的排列:$$$p = [2, 1, 3]$$$ 和 $$$p = [3, 1, 2]$$$。
在第二个测试用例中,唯一合适的排列是 $$$p = [4, 3, 2, 1]$$$。
在第四个测试用例中,可以证明没有排列$$$p$$$对应于数组$$$a$$$。