题面描述

给定一个长度为 $n$ 的数组 $a$，其中每个元素 $a_i$ 满足 $1 \le a_i \le n$。定义一个子序列的权值如下：

• 如果这个子序列不是严格递增的，那么它的权值为 $0$。
• 如果这个子序列是严格递增的，并且恰好是一个“排列子序列”（即：子序列本身的元素恰好构成 $\{1,2,\dots,k\}$ 的一个排列，且由于必须严格递增，因此只能是 $[1,2,\dots,k]$ 的形式），那么它的权值定义为该子序列的长度 $k$。

现在，我们要计算：数组 $a$ 中，所有满足上述“排列子序列”条件的子序列，它们的权值之和。最后结果需对 $10^9+7$ 取模。

题目内容

小苯定义一个排列的权值为:

• 如果排列不满足严格上升，则权值为$0$。

• 否则，严格上升的排列其权值为:排列的长度。

  现在小苯有个长为$n$的$a$数组，他想知道$a$中所有“排列”子序列 (即:此子序列是一个排列)的权值之和，请你帮他算一算吧。

输入描述

每个测试文件内都包含多组测试数据。

第一行一个正整数 $T(1 <T<100)$，表示测试数据的组数

接下来对于每组测试数据，输入包含两行。

第一行一个正整数$n(1≤n≤2×10^5)$，表示数组$a$的长度。

第二行$n$个整数$a_i(1 ≤ a_i≤n)$，表示数组$a$。

(保证所有测试数据中$n$的总和不超过$3×10^5$。)

输出描述

输出$T$行，每行一个整数表示当前测试用例的答案，即:所有“排列”子序列的权值之和。

(注意:由于答案可能很大，因此你只要输出答案对$1000000007$取模的值即可。)

样例1

输入

1
3
1 1 2

输出

6

说明

所有的“排列”子序列有:

{$1$},{$1$},{$1, 2$},{$1,2$}权值求和为$6$。