You are given an array $$a$$ of size $$n$$. The compressed version of an array is defined as replacing the occurance of consecutive equal integers with the single occurance.

Example: For \(a = [ 1, 1, 2, 2, 1, 1 ]\), the compressed version will be \([1,2,1]\).

The compressed number of an array is defined as number of ways to remove some non-empty subsequence of indexes from the initial array to make it compressed. Two ways are considered different if the sequence of indexes deleted from the array was different, the order of removing does not matter.

Calculate the sum of compressed number for all subarrays of the array \(a\). Since the sum may be large, print it modulo \(10^9+7\).

Example: For \(a = [ 3,3,3,3 ]\), the subarrays with the compressed numbers are as follows:

There are 4 subarrays of type $$ [3]$$. The compressed number is 0 as it is already compressed.
There are 3 subarrays of type $$ a=[3,3]$$. The compressed number is 2 as either of the index can be deleted. So, the sum of compressed number would be 6.
There are 2 subarrays of type $$ a=[3,3,3]$$. the compressed number is 3 as either of the sequence of indices $$[1,2], [ 1,3]$$ or $$[2,3]$$ can be deleted. So, the sum of compressed number would be 6.
There is 1 subarray $$ [3,3,3,3]$$ with the compressed number 4.
So, the sum of compressed number of all subarrays is 16.

Input format

The first line contains an integer $$t$$ denoting the number of test cases.
The first line of each test case contains an integer $$n$$ denoting the size of the array $$a$$.
The second line of each test case contains $$n$$ space-separated integers denoting the elements of array $$a$$.

Output format

Print a single integer for each test case denoting the sum of compressed number for all the subarrays of the array $$a$$.

Constraints

\(\\1 \le t \le 10 \\1 \le n \le 10^5 \\1 \le a[i] \le 10^5\)