Problem Description

Given a sequence (S_1, S_2, ..., S_N) (1 <= S_i <= 1,000,000,000, S_i != S_j), count the number of W, which can be regarded as a quintuple (a, b, c, d, e) satisfying a < b < c < d < e, S_b < S_c < S_a, S_d < S_c < S_e.

Input

The beginning of the input is an integer T, which is the number of test cases. T cases are followed. The first line of each test case is an integer N (1 <= N <= 100,000), which denotes the length of the sequence. The second line is N integer S_1, S_2, ..., S_N, which denote the sequence.

Output

For each test case, print a line contains a single integer which is the number of W, modulo 1,000,000,007.

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

1
3

Author

God of moe -- GXX