"I hide in plain sight, just as you".

Gus Fring has earned a huge profit from Los Pollos Hermanos and he wishes to celebrate. He loves watching horse-riding, hence he bought $N$ horses.
One day he organizes a horse-riding competition to celebrate the deal with Don Eladio.

There are $N$ horses taking part in the competition with speeds of $A${$1$}$,$ $A$ respectively. It is given that all speeds are distinct.}$,$ $...,$ $A$_{$N$

Multiple races are being conducted and it is not mandatory for each horse to participate in every race.

For the $i$^{$th$} horse, find the number of subsets with size $≥$ $2$ such that if a race were to be conducted between horses in this subset then the $i$^{$th$} horse would finish in the top three.

For subsets of size 2 the runner should finish either 1st or 2nd. There is no 3rd position when the size of the subset is 2.

Since the answer might be quite large, compute it, modulo $1000000007$ $(10^{9}+7)$.

------ Input: ------

First line will contain $T$, number of testcases. Then the testcases follow.
First line of each testcase contains of a single integer $N$ denoting the number of horses.
The second line of each testcase contains $N$ space-separated integers $A${$1$}$,$ $A$, denoting the speeds of the horses. }$,$ $...,$$A$_{$N$

------ Output: ------
For each testcase, output a single line containing $N$ space separated integers , where the $i$^{$th$} integer denotes the number of subsets of size $≥$ $2$ modulo $(10^{9}+7)$, such that the $i$^{$th$} horse finishes in the top three.

------ Constraints ------
$1 ≤ T ≤ 5000$
$2 ≤ N ≤ 10^{5}$
$1 ≤ A[i] ≤ 10^{9}$
All speeds are distinct
Sum of N over all test cases does not exceed $5*10^{5}$

----- Sample Input 1 ------
1
4
4 2 3 1
----- Sample Output 1 ------
7 7 7 6
----- explanation 1 ------
For the 1st horse the 7 subsets are- $ [4,2,3,1],[4,2,3],[4,2,1],[4,3,1],[4,2],[4,1],[4,3]$
For the 2nd horse the subsets are- $[4,2,3,1],[4,2,3],[4,2,1],[2,3,1],[2,4],[2,1],[2,3]$
For the 3rd horse the subsets are- $[4,2,3,1],[4,2,3],[3,2,1],[4,3,1],[3,2],[3,1],[4,3]$
For the 4th horse the subsets are- $[1,2,3],[4,2,1],[4,3,1],[1,2],[4,1],[1,3]$

见题面

见题面