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.

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 $ .

For each test case, output the number of suitable permutations modulo $ 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 $ .