問題文

いろはちゃんはペットを育てるゲームにはまっています。

いろはちゃんはペットとして高橋君を飼っており、はじめ高橋君の 強さ は $X$ 、経験値 は $0$ です。 これらの値は次の $2$ 種類の特訓によって増加します。

• カコモンジムに通う：強さが $A$ 倍になり、経験値は $1$ 増える。
• AtCoderジムに通う：強さが $B$ 増え、経験値は $1$ 増える。

高橋君は強さが $Y$ 以上になると進化しますが、進化しない方がかわいいといろはちゃんは思っています。

そこで、強さが $Y$ 以上にならないように高橋君に特訓を課すとき、経験値の最大値を求めてください。

制約

• $1 \\leq X < Y \\leq 10^{18}$
• $2 \\leq A \\leq 10^9$
• $1 \\leq B \\leq 10^9$
• 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

$X$ $Y$ $A$ $B$

出力

与えられた条件の下での経験値の最大値を出力せよ。

入力例 1

4 20 2 10

出力例 1

2

最初、高橋君の強さは $4$ です。次のような特訓方法によって、経験値を $2$ にすることができます。

• まず カコモンジムに通うことで、高橋君の強さは $8$、経験値は $1$ になります。
• 次に、AtCoderジムに通うことで、高橋君の強さは $18$、経験値は $2$ になります。

どのような特訓方法によっても、経験値を $2$ より大きくすることはできません。

入力例 2

1 1000000000000000000 10 1000000000

出力例 2

1000000007

オーバーフローに注意してください。