CF1621G.Weighted Increasing Subsequences

You are given the sequence of integers $a_1, a_2, \ldots, a_n$ of length $n$.

The sequence of indices $i_1 \lt i_2 \lt \ldots \lt i_k$ of length $k$ denotes the subsequence $a_{i_1}, a_{i_2}, \ldots, a_{i_k}$ of length $k$ of sequence $a$.

The subsequence $a_{i_1}, a_{i_2}, \ldots, a_{i_k}$ of length $k$ of sequence $a$ is called increasing subsequence if $a_{i_j} \lt a_{i_{j+1}}$ for each $1 \leq j \lt k$.

The weight of the increasing subsequence $a_{i_1}, a_{i_2}, \ldots, a_{i_k}$ of length $k$ of sequence $a$ is the number of $1 \leq j \leq k$, such that exists index $i_k \lt x \leq n$ and $a_x \gt a_{i_j}$.

For example, if $a = [6, 4, 8, 6, 5]$, then the sequence of indices $i = [2, 4]$ denotes increasing subsequence $[4, 6]$ of sequence $a$. The weight of this increasing subsequence is $1$, because for $j = 1$ exists $x = 5$ and $a_5 = 5 \gt a_{i_1} = 4$, but for $j = 2$ such $x$ doesn't exist.

Find the sum of weights of all increasing subsequences of $a$ modulo $10^9+7$.

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

长度为 $k$ 的下标序列 $i_1 \lt i_2 \lt \ldots \lt i_k$ 表示序列 $a$ 的一个长度为 $k$ 的子序列 $a_{i_1}, a_{i_2}, \ldots, a_{i_k}$。

序列 $a$ 的一个长度为 $k$ 的子序列 $a_{i_1}, a_{i_2}, \ldots, a_{i_k}$ 称为递增子序列，当且仅当对每个 $1 \leq j \lt k$，均有 $a_{i_j} \lt a_{i_{j+1}}$。

序列 $a$ 的一个长度为 $k$ 的递增子序列 $a_{i_1}, a_{i_2}, \ldots, a_{i_k}$ 的权重定义为满足如下条件的下标 $j$（其中 $1 \leq j \leq k$）的个数：存在某个下标 $x$ 满足 $i_k \lt x \leq n$ 且 $a_x \gt a_{i_j}$。

例如，若 $a = [6, 4, 8, 6, 5]$，则下标序列 $i = [2, 4]$ 表示 $a$ 的一个递增子序列 $[4, 6]$。该递增子序列的权重为 $1$，因为对 $j = 1$，存在 $x = 5$ 使得 $a_5 = 5 \gt a_{i_1} = 4$；但对 $j = 2$，不存在满足条件的 $x$。

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

The first line contains a single integer $t$ ($1 \leq t \leq 1000$) — the number of test cases.

The first line of each test case contains the single integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the length of the sequence $a$.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$) — the sequence $a$.

It is guaranteed that the sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \leq t \leq 1000$）——测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 2 \cdot 10^5$）——序列 $a$ 的长度。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^9$）——序列 $a$。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

For each test case, print the sum of weights of all increasing subsequences $a$ modulo $10^9+7$.

对于每个测试用例，输出所有递增子序列 $a$ 的权重之和对 $10^9+7$ 取模的结果。

In the first test case the following increasing subsequences of $a$ have not zero weight:

• The weight of $[a_1] = [6]$ is $1$.
• The weight of $[a_2] = [4]$ is $1$.
• The weight of $[a_2, a_3] = [4, 8]$ is $1$.
• The weight of $[a_2, a_4] = [4, 6]$ is $1$.

The sum of weights of increasing subsequences is $4$.

In the second test case there are $7$ increasing subsequences of $a$ with not zero weight: $3$ with weight $1$, $3$ with weight $2$ and $1$ with weight $3$. The sum of weights is $12$.

在第一个测试用例中，数组 $a$ 的以下严格递增子序列的权重不为零：

• $[a_1] = [6]$ 的权重为 $1$。
• $[a_2] = [4]$ 的权重为 $1$。
• $[a_2, a_3] = [4, 8]$ 的权重为 $1$。
• $[a_2, a_4] = [4, 6]$ 的权重为 $1$。

所有严格递增子序列的权重之和为 $4$。

在第二个测试用例中，数组 $a$ 共有 $7$ 个权重不为零的严格递增子序列：其中 $3$ 个权重为 $1$，$3$ 个权重为 $2$，$1$ 个权重为 $3$。权重之和为 $12$。