問題文


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

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

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

制約


  • は素数である

入力


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


...

出力


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

入力例1


2
2 2

出力例1


8

です. この時, の8通りが答えとなります.

入力例2


2
2 3

出力例2


15

です.

入力例3


7
2 2 3 7 7 17 998244341

出力例3


993855353

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

提出


Go (1.14)