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,
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.
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.
Start from 1 again.
Now before you start, you are wondering expected how many candies you will have after finishing this algorithm.
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.
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.
Input | Output |
---|---|
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.