Sum of Compressed Number for All Subarrays

For each contiguous subarray of the array, adjacent equal values compress into a single representative. The compressed number of that subarray is the number of different choices that produce the standard compressed array by keeping exactly one index in each maximal run of equal values and deleting the other indices of that run; if the subarray is already compressed, it is 0. Find the sum of the compressed numbers of all subarrays modulo 1,000,000,007.

输入格式

The first line contains t; then each test case gives n followed by n integers a[i]. Source constraints: 1≤t≤10, 1≤n≤100000, 1≤a[i]≤100000. This site additionally adds total n≤200000.

输出格式

For each test case, output one line with the answer modulo 1,000,000,007.

样例 1

输入：

1
5
6 7 3 6 6

输出：

8

样例 2

输入：

1
2
4 4

输出：

2

样例 3

输入：

1
4
3 3 3 3

输出：

16