给定长度为 $$$n$$$ 的整数序列 $$$a_1, a_2, \ldots, a_n$$$。
长度为 $$$k$$$ 的索引序列 $$$i_1 < i_2 < \ldots < i_k$$$ 表示序列 $$$a$$$ 的长度为 $$$k$$$ 的子序列 $$$a_{i_1}, a_{i_2}, \ldots, a_{i_k}$$$。
如果对于每个 $$$1 \leq j < k$$$,$$$a_{i_j} < a_{i_{j+1}}$$$,则序列 $$$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 \leq k$$$的个数,使得存在索引$$$i_k < x \leq n$$$并且$$$a_x > a_{i_j}$$$。
例如,如果 $$$a = [6, 4, 8, 6, 5]$$$,则索引序列 $$$i = [2, 4]$$$ 表示序列 $$$a$$$ 的递增子序列 $$$[4, 6]$$$。这个递增子序列的权重是 $$$1$$$,因为对于 $$$j = 1$$$ 存在 $$$x = 5$$$ 和 $$$a_5 = 5 > a_{i_1} = 4$$$,但对于 $$$j = 2$$$ 这样的 $$$x$$$ 不存在。
求 $$$a$$$ 模 $$$10^9+7$$$ 的所有递增子序列的权重总和。
输入
第一行包含一个整数 $$$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$$$。
输出
对于每个测试用例,打印所有递增子序列 $$$a$$$ 模 $$$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$$$ 的以下递增子序列的权重不为零:
- $$$[a_1] = [6]$$$ 的权重为 $$$1$$$。
- $$$[a_2] = [4]$$$ 的权重为 $$$1$$$。
- $$$[a_2, a_3] = [4, 8]$$$ 的权重为 $$$1$$$。
- $$$[a_2, a_4] = [4, 6]$$$ 的权重为 $$$1$$$。
在第二个测试用例中,$$$a$$$ 的权重不为零的 $$$7$$$ 递增子序列:$$$3$$$ 的权重为 $$$1$$$、$$$3$$$ 的权重为 $$$2$$$ 和 $$$1$$$ 的权重为 $$$3$$$。权重总和为$$$12$$$。