Practice on Toph

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

Divide Candy Again

By ridowan007 · Limits 3s, 512 MB

There are N boxes with candies numbered from 1 to N. The number of candies in the boxes numbered 1 to N are 1, 1, 2, 3, 5, 8, 13, 21,,, Fi,,, FN. That is the if (i-2)th box has Fi-2 candy and (i-1)th box has Fi-1 candy then ith box has

Fi = Fi-1 + Fi-2 candies.

The candies need to be divided between two sisters Mouri and Oishi. But there is a problem, they are quarreling. None of them will take candy from box i if another one has taken candy from it. Now to divide the candies you have decided to follow the below algorithm,

  1. If there is no box with candy left, you are done. Otherwise choose one of the boxes. Probability of choosing each box is equal. Let' assume the chosen box has F candies in it.

  2. You will do one of the following randomly. Probability of doing any of them is equal,

    i. Choose a random number C from 1 to F uniformly(the probability of choosing any of the F numbers are same) and give C candies to Mouri. Take the rest of them(if any).

    ii. Choose a random number C from 1 to F uniformly(the probability of choosing any of the F numbers are same) and give C candies to Oishi. Take the rest of them(if any).

    iii. Take all candies for yourself.

  3. Start from 1 again.

Now before you start, you are wondering expected how many candies you will have after finishing this algorithm.

Input

First line of the input is T(<=100000), then T test cases follows. Each case have only one line containing a positive integers N (1 <= N <= 1016) the number of candy boxes.

Output

For each test case print one line in format "Case I: E" where I is case number and E is expected number of candies you will take. As the answer can be very big and irrational(fraction) output it by multiplying the answer with 24 and take mod by 1000000007. It is guaranteed that input will be such that multiplying the result with 24 will give a positive integer.

Sample

InputOutput
3
1
2
3
Case 1: 8
Case 2: 16
Case 3: 40

In the first case, there is only one box with 1 candy. ⅓ probability that you will take the 1 candy. So expected candy taken will be ⅓. Now multiplying it with 24 gives ⅓ * 24 = 8.

In the second case, the expected number of candy you will take is ⅔. Now multiplying it with 24 gives ⅔ * 24 = 16.

Discussion

Statistics


76% Solution Ratio

moshiur.bdEarliest, Dec '16

habijabiFastest, 0.0s

oneoff.lucR74wIlnLightest, 131 kB

habijabiShortest, 751B

Submit

Login to submit

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