G. Now I Know You Are Blind Man, But You Gotta See This
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Naseem has $$$n$$$ children. Instead of giving each child his own name, he gave each child $$$i$$$ a number $$$a_i$$$. Note that there might be two children with the same number. More formally, for $$$i$$$ and $$$j$$$ where $$$i \ne j$$$, $$$a_i$$$ can be equal to $$$a_j$$$

Sometimes, Naseem gets back home and sees that some children went to enjoy their life (like going to the playground, solve some codeforces problems etc..), so he gets worried and start to check the smallest non-negative integer $$$x$$$ such that there is no child with number $$$x$$$ currently at home (which is called the MEX). and goes looking for children with their number equal to this MEX.

This process is tiring for him, especially that his eyes does not function that good. He asked you to write a program that is given $$$n$$$ and an array $$$a$$$ of length $$$n$$$, it finds the sum of MEX of every subsequence of $$$a$$$.

A subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements

The MEX (minimum excluded) of a set is the smallest non-negative integer that does not belong to the set.

Input

The first line of the input contains a single integer number $$$t$$$ $$$(1 \le t \le 3 \times 10^4)$$$. The number of test cases.

The first line of each test case contains a single integer number $$$n$$$ $$$(1 \le n \le 2 \times 10^5)$$$. The number of children Naseem has

The second line of each test case contains $$$n$$$ space-separated integer numbers $$$a_1, a_2 \dots a_n$$$ $$$(0 \le a_i \le 10^9)$$$, where $$$a_i$$$ is the number assigned to the $$$i-th$$$ child.

It is guaranteed that the sum of $$$n$$$ and the sum of $$$m$$$ over all of the test cases does not exceed $$$2 \times 10^5$$$.

Output

For each test case print a single line containing a single integer number. The sum of MEX of every subsequence of $$$a$$$. As the answer might be large, print the answer modulo $$$10^9 + 7$$$.

Examples
Input
1
3
0 1 2
Output
7
Input
2
4
0 3 1 3
5
1 3 2 3 2
Output
12
0
Note

In the first and only test case, the array $$$a$$$ has $$$8$$$ subsequences:

$$$- $$$ An empty subsequence, its MEX is $$$0$$$.

$$$- [0]$$$, its MEX is $$$1$$$.

$$$- [1]$$$, its MEX is $$$0$$$.

$$$- [2]$$$, its MEX is $$$0$$$.

$$$- [0, 1]$$$, its MEX is $$$2$$$.

$$$- [0, 2]$$$, its MEX is $$$1$$$.

$$$- [1, 2]$$$, its MEX is $$$0$$$.

$$$- [0, 1, 2]$$$, its MEX is $$$3$$$.

The sum of MEXs of all subsequences is $$$1+0+0+2+1+0+3 = 7$$$.