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