問題文
2以上の整数 M が与えられます.
0≤N<M,0≤P<M を満たす (N,P) の組み合わせは M2通りありますが,その内
P≡NP(modM)
を満たす (N,P) の組み合わせの数を 998244353 で割った余りを求めてください.
ただし,P≡NP(modM) は P を M で割った余りと N×P を M で割った余りが等しいことを意味しており,M の値は k 個の素数 A1,A2,⋯Ak を用いて以下の形式で与えられます.
M=∏i=1kAi
制約
- 1≤k≤105
- 2≤Ai<998244353
- Ai≤Ai+1 (i<n)
- Ai は素数である
入力
入力は以下の形式で標準入力から与えられる。
出力
答えを標準出力に1行で出力せよ。行末に改行を入れること。
入力例1
出力例1
M=4 です.
この時,(N,P)=(0,0),(1,0),(1,1),(1,2),(1,3),(2,0),(3,0),(3,2)
の8通りが答えとなります.
入力例2
出力例2
M=6 です.
入力例3
出力例3
答えを 998244353 で割った余りを出力してください.