TokenDoublingGame | Topcoder Archive

Problem Statement

You are playing a coin-flipping game. At the beginning of the game you are given an int N and a fair coin.

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

```
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.
```
13
```
```
Returns: 444154848
```
Here, the exact answer is 2795844533351/105312396244, which means that the return value is (2795844533351 * 105312396244^(-1)) mod (10^9 + 7).

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.