Practice on Toph

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

An Act of Uniformly Random Kindness

By Sherlock221b · Limits 2s, 512 MB

After selling all the bitcoins that you bought back in 2010, you now find yourself with a huge amount of money. Of course, you've always been a philanthropist at heart and thus have decided to donate a fair amount of money to people who are less fortunate than you.

You've stored all the money in N bags (conveniently numbered from 1 to N). The bags are arranged from left to right; the leftmost bag being 1 and the rightmost being N. You've decided to donate some of the bags (with the money inside them). But due to your indecisive nature, you haven't been able to make up your mind as to which bags you want to donate to the poor. So you've decided to pick bags at random (to be more specific, uniformly random).

Here's how you are going to do this. You will pick a bag at random and donate all its money to the poor. And then, the money inside all the bags to the right of the chosen bag (if there are any) will be added to your bank account. So the chosen bag and all the bags to its right will be discarded. Then with the remaining bags, you will continue this same process until there are no more bags left.

Now you're wondering what is the expected amount of money that will be added to your bank account. 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.Q-1 (mod 109+7).


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 number of bags. The second line of each test case contains N space seperated integers denoting the amount of money in the N bags.


1 <= T <= 25

2 <= N <= 105

1 <= Amount of money in each bag <= 109


For each test case, print a single line containing a single integer - the expected amount of money that will be added to your bank account written as P.Q-1 (mod 109+7).


12 6
1 1 1


For the first case, the expected value is 3/1. So the answer is 3.1-1(mod 109+7) which is 3.

For the second case, the expected value is 7/6. So the answer is 7.6-1(mod 109+7) which is 166666669.



100% Solution Ratio

arknaveEarliest, Apr '20

Deshi_TouristFastest, 0.4s

YouKnowWhoLightest, 131 kB

hredhayxzShortest, 665B


Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.