問題文

2以上の整数 MM が与えられます. 0N<M,0P<M0 \leq N \lt M, 0 \leq P \lt M を満たす (N,P)(N, P) の組み合わせは M2M^2通りありますが,その内

PNP(modM)P \equiv NP \pmod M

を満たす (N,P)(N, P) の組み合わせの数を 998244353998244353 で割った余りを求めてください.

ただし,PNP(modM)P \equiv NP \pmod MPPMM で割った余りと N×PN \times PMM で割った余りが等しいことを意味しており,MM の値は kk 個の素数 A1,A2,AkA_1, A_2, \cdots A_k を用いて以下の形式で与えられます.

M=i=1kAiM = \prod_{i=1}^{k} A_i

制約

  • 1k1051 \leq k \leq 10^{5}
  • 2Ai<9982443532 \leq A_i \lt 998244353
  • AiAi+1A_i \leq A_{i+1} (i<n)(i \lt n)
  • AiA_i は素数である

入力

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

kk
A1A_1 A2A_2 ... AkA_k

出力

答えを標準出力に1行で出力せよ。行末に改行を入れること。

入力例1

2
2 2

出力例1

8

M=4M=4 です. この時,(N,P)=(0,0),(1,0),(1,1),(1,2),(1,3),(2,0),(3,0),(3,2)(N, P) = (0, 0), (1, 0), (1, 1), (1, 2), (1, 3), (2, 0), (3, 0), (3, 2) の8通りが答えとなります.

入力例2

2
2 3

出力例2

15

M=6M=6 です.

入力例3

7
2 2 3 7 7 17 998244341

出力例3

993855353

答えを 998244353 で割った余りを出力してください.

Submit


Go (1.21)