题目内容

给定一个长度为 $n$ 的整数序列 $a_1, a_2, \dots, a_n$，表示某个系统指标在连续时间点上的记录值。 对于任意一个区间 $[L, R]$（$1 \le L \le R \le n$），定义该区间的「累积代价」为从区间左端点开始逐步向右累加时，左端点到当前位置的最小值之和。形式化地，

请你计算所有可能的区间 $[L, R]$ 的累积代价之和，即

并将结果对 $1000000007$ 取模后输出。

约束条件：测试用例个数不超过 $10^5$；每个序列的长度 $n$ 不超过 $2 \times 10^5$；所有测试用例的序列长度总和不超过 $3 \times 10^5$；序列中的每个整数均在 $0$ 到 $10^9$ 之间。

输入描述

第一行包含一个整数 $q$，表示测试用例的个数。 接下来依次给出每个测试用例的数据： 每个测试用例的第一行包含一个整数 $n$，表示序列的长度； 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示序列中的各个元素。

输出描述

对于每个测试用例，输出一行一个整数，表示该测试用例中所有区间的累积代价之和对 $1000000007$ 取模的结果。

样例1

输入

1
1
0

输出

0

说明

序列长度为 1，唯一的区间为 [1,1]。该区间的累积代价 $C(1,1)=\min(a_1)=0$，因此所有区间的累积代价之和为 0。

样例2

输入

1
2
3 1

输出

8

说明

序列为 [3, 1]，共有 3 个区间。

• 区间 [1,1]：$C(1,1)=\min(3)=3$；
• 区间 [1,2]：$C(1,2)=\min(3)+\min(3,1)=3+1=4$；
• 区间 [2,2]：$C(2,2)=\min(1)=1$； 总和为 $3+4+1=8$。

样例3

输入

1
3
2 1 3

输出

15

说明

序列为 [2, 1, 3]，共有 6 个区间，分别计算累积代价：

• [1,1]：$\min(2)=2$；
• [1,2]：$\min(2)+\min(2,1)=2+1=3$；
• [1,3]：$\min(2)+\min(2,1)+\min(2,1,3)=2+1+1=4$；
• [2,2]：$1$；
• [2,3]：$\min(1)+\min(1,3)=1+1=2$；
• [3,3]：$3$； 总和为 $2+3+4+1+2+3=15$。