TUNA2026 東京Stage Welcome コンテスト (オープン) 2026/09/23 14:00 ~ 2026/09/23 18:00 4:00:00

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
252
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}\) を表しています。

サンプル