Limits 2s, 512 MB

Meena has an array of length N (1-indexed). The numbers of the array are arranged from left to right (the leftmost element's index being 1 and the rightmost's index being N).

Meena does the following until the array is completely empty: she will pick one number at random from all the remaining numbers of the array. The sum of all numbers to the right of the chosen number (if there are any) will be added to her score (initially, her score is 0). Then the chosen number and all the numbers to its right will be discarded from the array. Then with the remaining numbers of the array, she will continue the same process until the array is completely empty.

Your task is to find the expected value of Meena's score after she's done with the array. It can be shown that the expected value can be represented as P/Q where P and Q are co-prime integers. Print the value of P.Q1{\bf P.Q^{-1}} (mod 1000000007).

Input

The first line of input contains an integer T which denotes the number of test cases.

The first line of each test case contains a single integer N denoting the length of the array. The second line of each test case contains N space-separated integers A1A_1, A2A_2, A3A_3, … ANA_N denoting the numbers of the array.


Constraints:

1 ≤ T ≤ 25
2 ≤ N ≤ 10510^5
1 ≤ AiA_i10910^9 for 1 ≤ i ≤ N

Output

For each test case, first print the serial number of the test case, followed by Meena's expected score written as P.Q1{\bf P.Q^{-1}} (mod 1000000007). Please check the sample input-output section for formatting details.

Sample

InputOutput
2
2
4 8
3
1 1 1
Case 1: 4
Case 2: 166666669

Explanation:
For the first case, the expected value is 4/14/1. So the answer is 4.114.1^{-1} (mod 1000000007) which is 4.
For the second case, the expected value is 7/67/6. So the answer is 7.617.6^{-1}(mod 1000000007) which is 166666669.

Submit

Login to submit.

Statistics

89% Solution Ratio
BerlekampMassyEarliest, May '21
nusuBotFastest, 0.1s
kzvd4729Lightest, 131 kB
BerlekampMassyShortest, 676B
Toph uses cookies. By continuing you agree to our Cookie Policy.