Problem Statement

You are given integers $A,B,P,Q$.
Here, suppose that there exist real numbers $X,Y$ satisfying the following.

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

In this case, find $1$ integer $N$ between $2$ and $10^{18}$, inclusive, such that $X^N + Y^N \equiv P, X^{N-1} + Y^{N-1} \equiv Q\ (\mathrm{mod}\ 998244353 )$.

It is guaranteed that the input of this problem satisfies the following.

• $X,Y$ exist and are uniquely determined.
• For every integer $N$ greater than or equal to $1$, $X^N+Y^N$ is an integer.
• There exists an integer $N$ between $2$ and $10^{10}$, inclusive, that satisfies the condition.

Input

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

• $0 \leq A,B,P,Q < 998244353$
• All inputs are integers.

Output

Output $N$. If there are multiple solutions, you may output any of them.

Sample

13 42 559 85

3

2 1 2 2

1000000000000000000