xtq的棋盘
题目背景
自从二年级起,xtq就热爱棋类游戏。
题目描述
xtq有一个$1$行,$n+1$列的棋盘,从左到右编号为$0$到$n$。初始时刻,在$m$位置有一颗棋子。
xtq会在接下来的时间里随机操作。具体地说,如果某一秒棋子不位于$n$,那么他将有$prb$的概率将棋子向左移动一格,$1-prb$的概率向右移动一格;否则,他必然将棋子向左移动一格。
现在xtq想问你,期望多少秒之后棋子能够到达$0$。由于答案可能很大,并且为了避免不必要的精度误差,你只需要给出答案对于$10^9+7$取模的结果即可(可以证明,答案必然是一个有理数)。
输入输出格式
输入格式
一行四个正整数$n,m,p,q$。
其中,$p,q$表示$prb = \frac{p}{q}$。
输出格式
一行,一个正整数,表示期望移动次数对$10^9+7$取模的结果。
输入输出样例
输入样例 #1
3 1 1 3
输出样例 #1
13
说明
对于$20\%$的数据,$n\le 4, 1\le p\le q\le 4$而且保证答案在取模前是一个整数。
对于$40\%$的数据,$n\le 300$。
对于$70\%$的数据,$n\le 1000000$。
对于$100\%$的数据,$1\le m\le n\le 10^9, 1\le p\le q\le 10^9$并且$p,q$互质。
此外,在全部的数据点中,有$30\%$的数据是满足$prb = \frac{1}{2}$的。
有理数对质数$p$取模定义如下:
设$\frac{a}{b}$对$p$取模的结果为$x$,那么需要满足$0\le x<p$且$a \equiv bx (mod p)$。
保证对于$100\%$的数据,一定存在满足要求的$x$。