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$取模的结果。

3 1 1 3

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$。