Apple

We are going to distribute apples to n children. Every child has his/her desired number of apple ${A_1},{A_2},{A_3}, \cdots {A_n}$ ， ${A_i}$ indicates the i-th child’s desired number of apple. Those children should stand in a line randomly before we distribute apples. Assume that the i-th position is occupied by ${p_i} - th$ child, i.e. from left to right the id of the children are ${p_1},{p_2},{p_3}, \cdots {p_n}$，So their desired number of apple are ${A_{{p_1}}},{A_{{p_2}}},{A_{{p_3}}},
\cdots {A_{{p_n}}}$. We will distribute ${A_{{p_1}}}$ apples to the left most child，and for the i-th (i>1)child，if there exists a j which makes j < i and ${A_{p_j}} > {A_{{p_i}}}$ true, we will distribute no apples to him/her，otherwise we will distribute ${A_{{p_i}}}$ apples to him/ner. So for a certain permutation there exist a certain number of apples we should distribute. Now we want to know how many apples we should distribute for all possible permutation.
Note: two permutations are considered different if and only if there exists at least a position in which two children’s desired number of apple are different.

Multi test cases，the first line contains an integer T which indicates the number of test cases. Then every case occupies two lines.
For each case, the first line contains an integer n which indicates there are n children.
The second line contain n integers ${A_1},{A_2},{A_3}, \cdots {A_n}$ indicate n children’s desired number of apple.
[Technique specification]
All numbers are integer
1<=T<=20
1<=n<=100000
1<=Ai<=1000000000

For each case，output occupies one line，the output format is Case #x: ans, x is the data number starting from 1，ans is the total number of apple modular 1000000007.

2
2
2 3
3
1 1 2

Case #1: 8
Case #2: 9

For the second case, all possible permutation and

corresponding distributed apples are
(1,1,2),4
(1,2,1),3
(2,1,1),2
So the total number of apple is 2+3+4=9

BestCoder Round #26