Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Bi-Element Subsequence

By upobir · 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][3, 5, 6] is a subsequence of [1,2,3,4,5,6][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 109+710^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 TT, denoting the number of testcases.

The iith testcase will contain two lines. The first line will contain nn, the number of elements in the sequence. The next line will contain a sequence of nn space-separated positive integers.

1T1051 \leq T \leq 10^5

1n1051 \leq n \leq 10^5

11 \leq elements of the sequence 109\leq 10^9

11 \leq sum of nn over all test cases 105\leq 10^5

Output

For iith case output the answer modulo 109+710^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][2, 3], [1][1], [1,1,2,2][1, 1, 2, 2] have at most two distinct number. But [2,3,5][2, 3, 5] have more than two distinct numbers

    Discussion

    Statistics


    82% Solution Ratio

    Farhan20Earliest, 2w ago

    freedom_seekerFastest, 0.0s

    Zobayer_AbedinLightest, 1.7 MB

    mustafiz_voidShortest, 762B

    Submit

    Login to submit

    Editorial

    First note that, taking any non-empty subset of {1,2,⋯ ,n}\{ 1, 2, \cdots, n \}{1,2,⋯,n}gives us a s...

    Toph uses cookies. By continuing you agree to our Cookie Policy.