题目内容

给定一个长度为 $n$ 的整数数组 $a$。对任意子数组区间 $[l,r]$，定义 $f(l,r) = \sum_{k=l}^{r} \left( \min_{i \in [l,k]} a_i \right)$。

请计算 $\sum_{1 \le l \le r \le n} f(l,r)$ 并将结果对 $10^9 + 7$ 取模后输出。

输入描述

每个测试文件包含多组测试数据。第一行输入一个整数 $T$（$1 \le T \le 10^5$）表示测试组数。接下来每组数据描述如下：

第一行输入一个整数 $n$（$1 \le n \le 2 \times 10^5$）。

第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n$（$0 \le a_i \le 10^9$）。

保证所有测试数据的 $n$ 之和不超过 $3 \times 10^5$。

输出描述

对于每组测试数据，输出一行一个整数，表示 $\sum_{1 \le l \le r \le n} f(l,r)$ 对 $10^9 + 7$ 取模后的结果。

样例1

输入

2
3
2 1 3
4
3 3 3 3

输出

15
60

说明

样例一：$a = [2,1,3]$。

$f(1,1) = \min\{2\} = 2$

$f(1,2) = \min\{2\} + \min\{2,1\} = 2 + 1 = 3$

$f(1,3) = \min\{2\} + \min\{2,1\} + \min\{2,1,3\} = 2 + 1 + 1 = 4$

$f(2,2) = \min\{1\} = 1$

$f(2,3) = \min\{1\} + \min\{1,3\} = 1 + 1 = 2$

$f(3,3) = \min\{3\} = 3$

总和为 $2 + 3 + 4 + 1 + 2 + 3 = 15$