Problem Statement
You are playing a coin-flipping game.
At the beginning of the game you are given an
The game starts with N tokens on the table and 1 token in your hand.
In each round of the game, you flip the coin and act according to the outcome:
- Heads: Discard your hand (the tokens disappear). Then, take two new tokens. Place one on the table and take the other into your hand. If there are now 2*N tokens on the table, the game ends.
- Tails: Let X be the number of tokens in your hand. Take another X tokens from the table into your hand. If the table becomes empty during or after you do that, the game ends.
The expected number of coin flips during this game can be represented as a reduced fraction A/B. Let B^(-1) be the inverse element to B, modulo 10^9 + 7. Compute and return the value (A * B^(-1)) modulo 10^9 + 7.
Definition
- Class:
- TokenDoublingGame
- Method:
- expectation
- Parameters:
- int
- Returns:
- int
- Method signature:
- int expectation(int N)
- (be sure your method is public)
Notes
- For each valid input the value B^(-1) exists.
Constraints
- N will be between 1 and 100,000, inclusive.
Examples
100000
Returns: 386506648
99999
Returns: 662623410
1
Returns: 1
The game ends after the first coin flip, regardless of its outcome.
2
Returns: 333333339
The exact answer as a reduced fraction is 10/3. Computing modulo 10^9 + 7, we have 10 * 3^(-1) = 10 * 333,333,336 = 333,333,339.
3
Returns: 86956528
4
Returns: 143133472
5
Returns: 531208514
70
Returns: 486692849
148
Returns: 666044228
67
Returns: 804558285
262
Returns: 309970392
27
Returns: 465154386
275
Returns: 26615014
274
Returns: 896355842
221
Returns: 824305511
210
Returns: 161846485
58
Returns: 654834340
50575
Returns: 253487369
21751
Returns: 707262782
73252
Returns: 576761676
17612
Returns: 379246407
18651
Returns: 94871607
99751
Returns: 738254848
36700
Returns: 140916593
22852
Returns: 40486574
29660
Returns: 887215598
89924
Returns: 305815617
96159
Returns: 61482976
50172
Returns: 908406394
68305
Returns: 34282102
56303
Returns: 735678350
93872
Returns: 554694722
72951
Returns: 329809157
95429
Returns: 502874877
95827
Returns: 583227061
64640
Returns: 916664936
75575
Returns: 912198438
58858
Returns: 932472953
91775
Returns: 130113917
50452
Returns: 390570688
62394
Returns: 704738027
64202
Returns: 820058898
99809
Returns: 923597862
99833
Returns: 349502302
99841
Returns: 364463649
99914
Returns: 944687452
99866
Returns: 236232328
13
Returns: 444154848
Here, the exact answer is 2795844533351/105312396244, which means that the return value is (2795844533351 * 105312396244^(-1)) mod (10^9 + 7).