P ≡ NP

2以上の整数 が与えられます． を満たす の組み合わせは 通りありますが，その内

を満たす の組み合わせの数を で割った余りを求めてください．

ただし， は を で割った余りと を で割った余りが等しいことを意味しており， の値は 個の素数 を用いて以下の形式で与えられます．

• は素数である

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

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

2
2 2

8

です． この時， の8通りが答えとなります．

2
2 3

15

です．

7
2 2 3 7 7 17 998244341

993855353

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