Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Meena and Random Choice

By Sherlock221b · 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.

    Discussion

    Statistics


    100% Solution Ratio

    BerlekampMassyEarliest, 1w ago

    BerlekampMassyFastest, 0.2s

    BerlekampMassyLightest, 918 kB

    BerlekampMassyShortest, 676B

    Submit

    Login to submit