#abc298e. [abc298_e]Unfair Sugoroku
[abc298_e]Unfair Sugoroku
Problem Statement
Takahashi and Aoki will play a game of sugoroku.
Takahashi starts at point , and Aoki starts at point . They will take turns throwing dice.
Takahashi's die shows with equal probability, and Aoki's shows with equal probability.
When a player at point throws his die and it shows , he goes to point .
The first player to reach point wins the game.
Find the probability that Takahashi wins if he goes first, modulo .
How to find a probability modulo It can be proved that the sought probability is always rational. Additionally, the constraints of this problem guarantee that, if that probability is represented as an irreducible fraction , then is indivisible by .
Here, there is a unique integer between and such that . Report this .
Constraints
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
Output
Print the answer.
Sample Input 1
4 2 3 3 2
Sample Output 1
665496236
If Takahashi's die shows or in his first turn, he goes to point and wins.
If Takahashi's die shows in his first turn, he goes to point , and Aoki will always go to point in the next turn and win.
Thus, Takahashi wins with the probability .
Sample Input 2
6 4 2 1 1
Sample Output 2
1
The dice always show .
Here, Takahashi goes to point , Aoki goes to point , and Takahashi goes to point , so Takahashi always wins.
Sample Input 3
100 1 1 10 10
Sample Output 3
264077814