問題文

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

• $X\le 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$ が存在する。

入力

$ABPQ$

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

出力

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

サンプル

13 42 559 85

3

2 1 2 2

1000000000000000000