Time Limit: 5.0 s

Memory Limit: 512.0 MB

Description

A sequence B is called good if it contains at least 3 elements and \(COUNT(MAX(B)) = 1\) (the maximum element occurs only once) also the maximum element is not located at the edge of the sequence.

For example :
{1,3,3,2} is not good because max element 3 occurs twice
{3,2,2} and {1,2,3} both are not good because max element is located in the edge.
{2,5} is not good because it has a length less than 3

some good sequences : {1,3,2}, {3,3,2,6,1}, {2,2,5,2}

You are given an array of \(N\) integers. Calculate the number of good subsequences of the array. Since the answer can be too large , print it after modulo \(10^9+7\)

note: B is a subsequence of array A, if B can be obtained by deleting some elements from A without changing the order.
Two subsequence are different if there exist any index \(i\) (\(1<=i<=N\)) which is present in one sequence and absent in another.

Input

first line takes an integer \(T\) : number of testcases
First line of each testcase takes an integer \(N\) : size of the array
second line of each testcase takes \(N\) integers \(A_1,A_2,A_3...A_n\) : elements of the array

\(1 <= T <= 10000\)
\(1 <= N <= 2*10^5\)
\(1 <= A_i <= N\)

Output

for each testcase print the number of possible good subsequence modulo \(10^9+7\)

Sample

2
2
1 2
4
1 4 2 1

0
4

first testcase:
it is impossible to chose any sequence of size at least 3

second testcase:
all possible good sequences are
{1,4,2}
{1,2,1}
{1,4,2,1}
{1,4,1}