G. Weighted Increasing Subsequencestime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are given the sequence of integers a_1, a_2, \ldots, a_n of length n. The sequence of indices i_1 < i_2 < \ldots < 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} < a_{i_{j+1}} for each 1 \leq j < 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 < x \leq n and a_x > 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 > 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.InputThe 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.OutputFor each test case, print the sum of weights of all increasing subsequences a modulo 10^9+7.ExampleInput
4
5
6 4 8 6 5
4
1 2 3 4
3
3 2 2
4
4 5 6 5
Output
4
12
0
6
NoteIn 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.
4
5
6 4 8 6 5
4
1 2 3 4
3
3 2 2
4
4 5 6 5

4 12 0 6 
['data structures', 'dp', 'math', '*3200']