加权递增子序列

• 时间限制：1 秒
• 内存限制：256 MiB

题目描述

给定一个长度为 $n$ 的整数序列 $a_1,a_2,\ldots,a_n$。

下标序列 $i_1<i_2<\cdots<i_k$ 表示子序列 $a_{i_1},a_{i_2},\ldots,a_{i_k}$。若对所有 $1\le j<k$ 都有 $a_{i_j}<a_{i_{j+1}}$，则称它为递增子序列。

一个递增子序列的权值，是满足下述条件的元素 $a_{i_j}$ 的个数：存在下标 $x$，使得 $i_k<x\le n$ 且 $a_x>a_{i_j}$。

求序列 $a$ 的所有非空递增子序列的权值之和，并对 $10^9+7$ 取模。

输入格式

第一行一个整数 $t$，表示测试用例数。

每个测试用例的第一行一个整数 $n$，第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

对每个测试用例输出一行一个整数，表示答案对 $10^9+7$ 取模的结果。

样例输入 1

4
5
6 4 8 6 5
4
1 2 3 4
3
3 2 2
4
4 5 6 5

样例输出 1

4
12
0
6

样例解释

在第一个测试用例中，权值非零的递增子序列为 $[a_1]$、$[a_2]$、$[a_2,a_3]$ 和 $[a_2,a_4]$，每个权值均为 $1$，故答案为 $4$。

数据范围

对所有数据，$1\le t\le1000$，$1\le n\le2\times10^5$，$1\le a_i\le10^9$，且单个输入文件内所有测试用例的 $n$ 之和不超过 $2\times10^5$。

每个测试点独立计分。