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.

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