問題文

整数 $A,B,P,Q$ が与えられます。
ここで、ある実数 $X,Y$ が存在して以下を満たすとします。

• $X \leq Y$
• $X+Y=A$
• $X \times Y=B$

このとき、 $X^N + Y^N \equiv P, X^{N-1} + Y^{N-1} \equiv Q\ (\mathrm{mod}\ 998244353 )$ を満たす $2$ 以上 $10^{18}$ 以下の整数 $N$ を $1$ つ求めてください。

なお、本問題の入力では以下が成り立つことが保証されます。

• $X,Y$ が存在し、かつ一意に定まる。
• $1$ 以上の整数 $N$ について $X^N+Y^N$ が整数となる。
• 条件を満たす $2$ 以上 $10^{10}$ 以下の整数 $N$ が存在する。

入力

$A\ \ B\ \ P\ \ Q$

• $0 \leq A,B,P,Q < 998244353$
• 入力は全て整数

出力

$N$ を出力してください。解が複数ある場合、どれを出力しても構いません。

サンプル

13 42 559 85

3

2 1 2 2

1000000000000000000