- All Contests
- ProjectEuler+
- Project Euler #227: The Chase

# Project Euler #227: The Chase

# Project Euler #227: The Chase

_{This problem is a programming version of Problem 227 from projecteuler.net}

"The Chase" is a game played with two -sided equiprobable dice and an even number of players.

The players sit around a table; the game begins with two opposite players having one die each. On each turn, the two players with a die roll it.

If a player rolls a , he passes the die to his neighbour on the left; if he rolls an , he passes the die to his neighbour on the right; otherwise, he keeps the die for the next turn.

The game ends when one player has both dice after they have been rolled and passed; that player has then lost.

In a game with players, what is the expected number of turns the game lasts? It can be proved that the answer is alsways rational, thus it can be represented as with natural coprime and . Give your answer as . It is guaranteed that is coprime with .

**Input Format**

Each test file contains one line with integers separated by single spaces: and .

**Constraints**

- is even

**Output Format**

Print exactly one integer number that is the answer to the problem.

**Sample Input 0**

```
6 6
```

**Sample Output 0**

```
113636380
```

**Explanation 0**

The real answer is . One could easily check that .