Chiaki 有一个序列 $A = \{a_1, a_2, \dots, a_n\}$。令 $\text{RMQ}(A, l, r)$ 为满足 $l \le i \le r$ 且 $a_i$ 是 $a_l, a_{l+1}, \dots, a_r$ 中最大值的最小下标 $i$。

如果两个长度均为 $n$ 的序列 $A$ 和 $B$ 对于所有的 $1 \le l \le r \le n$ 都满足 $\text{RMQ}(A, l, r) = \text{RMQ}(B, l, r)$，则称它们为 RMQ 相似。

对于给定的序列 $A = \{a_1, a_2, \dots, a_n\}$，定义序列 $B = \{b_1, b_2, \dots, b_n\}$ 的权重为：如果 $B$ 与 $A$ RMQ 相似，则权重为 $\sum_{i=1}^n b_i$，否则权重为 $0$。

若 $B$ 中的每个元素都是在 $0$ 到 $1$ 之间独立且均匀分布的随机实数，求 $B$ 的期望权重。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。对于每组测试数据：

第一行包含一个整数 $n$ ($1 \le n \le 10^6$)，表示序列的长度。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$)，表示该序列。

保证所有 $n$ 的总和不超过 $3 \times 10^6$。

输出格式

对于每组测试数据，输出答案作为一个有理数对 $10^9 + 7$ 取模的结果。

形式化地，题目保证在给定约束下，概率总是一个有理数 $\frac{p}{q}$（$p$ 和 $q$ 为整数且互质，$q$ 为正整数），且 $q$ 不能被 $10^9 + 7$ 整除。输出一个 $0$ 到 $10^9 + 6$ 之间的整数 $a$，使得 $p - aq$ 能被 $10^9 + 7$ 整除。

样例

输入 1

3
3
1 2 3
3
1 2 1
5
1 2 3 2 1

输出 1

250000002
500000004
125000001