CF2234E Vlad, Misha and Two Arrays

Vlad 想出了一个长度为 $n$ 的排列 $p$。之后，对每个 $i \in [1,n]$，他统计满足下述条件的区间 $(l,r)$ 的数量： $1 \le l \le r \le n$，且子数组 $p_l,p_{l+1},\dots,p_r$ 的最小值恰好等于 $p_i$，并把这个数量记作 $a_i$。 现在他把数组 $a_1,a_2,\dots,a_n$ 交给 Misha，让他还原排列 $p$。但 Misha 很快发现，不一定能唯一还原出排列 $p$。于是他打算算出**所有合法排列 $p$ 的数量**，结果对 $10^9+7$ 取模。请你帮他完成计算。 注意：Vlad 给出的数组 $a$ 有可能本身就是错的，此时合法排列数量为 $0$。

本题多组测试用例。 第一行输入测试用例数量 $t$（$1 \le t \le 10^4$）。 接下来依次给出每组用例： 每组第一行输入正整数 $n$（$1 \le n \le 5 \times 10^5$）——排列长度。 第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n$（$1 \le a_i \le 10^{12}$）——Vlad 给出的数组 $a$。 保证所有测试用例的 $n$ 之和不超过 $5 \times 10^5$。

对每组测试用例，输出合法排列的数量，结果对 $10^9+7$ 取模。

第一组样例存在恰好 $2$ 个合法排列：$p=[2,1,3]$ 和 $p=[3,1,2]$。 第二组样例仅有唯一合法排列：$p=[4,3,2,1]$。 第四组样例可以证明不存在任何对应的排列 $p$。