You are participating in a game show. In the final round, the host pulls up a large sequence of positive integers. And he asks you to count the number of non-empty subsequences of this sequence such that the subsequences have at most two distinct numbers. A subsequence of a sequence is created by erasing zero or more elements. For example is a subsequence of . The clock is ticking, the host is waiting, can you give him the answer? Since the answer can be large, even larger than a 64-bit integer, you have to divide that by and output the remainder. This is also known as the modulo operator.
Note that two subsequences are different if the indices of the removed elements are different.
The first line of input will be in integer , denoting the number of testcases.
The th testcase will contain two lines. The first line will contain , the number of elements in the sequence. The next line will contain a sequence of space-separated positive integers.
elements of the sequence
sum of over all test cases
For th case output the answer modulo in a separate line
Input | Output |
---|---|
3 3 1 2 2 10 1 1 2 2 3 3 4 4 5 5 5 1 2 3 4 5 | 7 105 15 |
In the first testcase, any subsequence has at most two distinct numbers.
In the second testcase, subsequence like , , have at most two distinct number. But have more than two distinct numbers