## LCC/Moose '20 Contest 2 S4 - Gamer Alan

View as PDF

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type

Alan is playing his least favourite game "Liquidate, Create, Conquer" over the winter break. Of course, Alan hates playing this game, but his current rank is unsatisfactory so he keeps playing. This game has a very simple ELO system, where winning a game nets you ELO point, while losing a game nets you elo points. Alan's desired rank is ELO points above his current ELO. Once he reaches this rank, he will immediately stop playing, but even if he doesn't reach this rank after games he will give up. Given that Alan has probability of winning each game, can you tell Alan the expected number of games he will play?

If you are unfamiliar with the concept of expected value, see here.

If you are unfamiliar with the concept of modular inverse, see here.

#### Input Specification

The only line of input contains integers: .

#### Output Specification

On one line, you are to output the expected number of games Alan will play. This value can be written as where , you are to print

No further constraints.

#### Sample Input

2 1 1 2

#### Sample Output

499122178

#### Sample Explanation

There is a chance that Alan wins his first game and ranks up. He plays game.

There is a chance that Alan loses his first game and thus plays a second game, after which he gives up. He plays games.