# Bi-Element Subsequence

Ada Lovelace National Gir...
Limits 1s, 512 MB

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 $[3, 5, 6]$ is a subsequence of $[1, 2, 3, 4, 5, 6]$. 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 $10^9+7$ 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.

## Input

The first line of input will be in integer $T$, denoting the number of testcases.

The $i$th testcase will contain two lines. The first line will contain $n$, the number of elements in the sequence. The next line will contain a sequence of $n$ space-separated positive integers.

$1 \leq T \leq 10^5$

$1 \leq n \leq 10^5$

$1 \leq$ elements of the sequence $\leq 10^9$

$1 \leq$ sum of $n$ over all test cases $\leq 10^5$

## Output

For $i$th case output the answer modulo $10^9+7$ in a separate line

## Sample

InputOutput
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 $[2, 3]$, $[1]$, $[1, 1, 2, 2]$ have at most two distinct number. But $[2, 3, 5]$ have more than two distinct numbers

### Statistics

82% Solution Ratio
Farhan20Earliest, 10M ago
freedom_seekerFastest, 0.0s
Zobayer_AbedinLightest, 1.7 MB
mustafiz_voidShortest, 762B
Toph uses cookies. By continuing you agree to our Cookie Policy.