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
Subtasks
Subtask 1 (5%)
Subtask 2 (10%)
Subtask 3 (15%)
Subtask 4 (20%)
Subtask 5 (50%)
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.
Comments