Problem Description

所以，计算方案数，是不是一种计算几何呢？

给定一个长度为 $n$ 的排列 $p_1, p_2, ..., p_n$，保证 $1$ 到 $n$ 的每个整数恰好出现一次。

记 $mx_{l,r}$ 为区间 $[l, r]$ 的最大值，即 $mx_{l,r} = \max(p_l, p_{l+1}, ..., p_r)$。

求：

$$\sum_{l=1}^{n} \sum_{r=l}^{n} mx_{l,r} \times 2^{r-l+1}$$

由于答案可能很大，请对 $10^9 + 7$ 取模。

Input Format

第一行一个整数 $T$（$1 \le T \le 10^5$），表示数据组数。

每组数据：

第一行一个整数 $n$（$1 \le n \le 10^6$），表示排列长度。

第二行 $n$ 个整数 $p_1, p_2, ..., p_n$（$1 \le p_i \le n$），保证是一个排列。

保证所有数据的 $n$ 之和不超过 $10^6$。

Output Format

对每组数据，输出一行一个整数，表示答案对 $10^9 + 7$ 取模后的结果。

2
3
1 3 2
4
2 1 4 3

60
188