SOLVE

LATER

Charged Up Array

/

You are given with an array \(A\) of size \(N\).An element \(A_i\) is said to be **charged** if its value(\(A_i\)) is **greater than or equal to** \(K_i\). \(K_i\) is the total number of subsets of array \(A\), that consist of element \(A_i\).

**Total charge value **of the array is defined as summation of all charged elements present in the array mod \(10^9+7\).

Your task is to output the total charge value of the given array \(A\).

**INPUT FORMAT:**

The first line of input contains number of test cases \(T\).

The first line of each test case consists of \(N\), the size of the array.

Next line contains \(N\) space-separated integers corresponding to each element \(A_i\).

**OUTPUT FORMAT:**

For each test case, output a single number corresponding to total charge value of the given array.

**CONSTRAINTS:**

\(1 \le T \le100\\ 1 \le N \le 10^5\\ 0 \le A_i \le 10^{18}\\\)

Explanation

**CASE 1:**

Possible subsets are: {3}, {4}, {5}, {3,4}, {3,5}, {4,5}, {3,4,5}, {}.

Element 3 is present in 4 subsets. As 3<4, it is not charged.

Element 4 is present in 4 subsets. As 4>=4, it is charged.

Element 5 is present in 4 subsets. As 5>=4, it is charged.

Total charge=4+5=9

**CASE 2:**

Possible subsets are: {1}, {6}, {1,6}, {}.

Element 1 is present in 2 subsets. As 1<2, it is not charged.

Element 6 is present in 2 subsets. As 6>=2, it is charged.

Total charge=6

Time Limit:
2.0 sec(s)
for each input file.

Memory Limit:
256 MB

Source Limit:
1024 KB

Initializing Code Editor...