K Two Different Modulus

制限時間: 3 sec メモリ制限: 1024 MB

Two Different Modulus

Statement

正整数 \(N,M\) と非負整数 \(A,B\) が与えられます。

次の値を計算してください。

\(\displaystyle \left(\prod_{i=0}^{N-1}((Ai+B)\bmod M)\right)\bmod 998244353\)

ここで、\(x\bmod m\) は \(x\) を \(m\) で割った余りを表します。

Input

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

\(N~A~B~M\)

制約は以下の通りです。

\(1\leq N\leq 10^9\)
\(1\leq M\leq 10^9\)
\(0\leq A\leq 10^9\)
\(0\leq B\leq 10^9\)
入力はすべて整数

Output

計算結果を \(1\) 行に出力してください。

Examples

Input 1

4 4 3 9

Output 1

Input 2

46 8724 294 10007

Output 2

744202079

Input 3

998244352 1 1 998244353

Output 3

998244352

Input 4

600000000 998244353 206 924844033

Output 4

180124642

Input 5

1000000000 444444444 314159265 897932384

Output 5

422453182

Note

サンプル \(1\) について:

\(\displaystyle (3\bmod 9)\times(7\bmod 9)\times(11\bmod 9)\times(15\bmod 9)=3\times7\times2\times6=252\) です。したがって、答えは \(252\) です。

サンプル \(3\) について:

\(998244352!\equiv-1\pmod{998244353}\) を表しています。