AT_arc192_d [ARC192D] Fraction Line

正の有理数 $ x $ に対し、 $ f(x) $ を以下のように定義します。 > $ x $ を互いに素な正整数 $ P,Q $ を用いて $ \dfrac{P}{Q} $ と表したときの $ P\times Q $ の値 正整数 $ N $ と、長さ $ N-1 $ の正整数列 $ A=(A_1,A_2,\dots,A_{N-1}) $ が与えられます。 以下の条件をすべて満たす長さ $ N $ の正整数列 $ S=(S_1,S_2,\dots,S_N) $ を **良い数列** と呼ぶことにします。 - $ 1\leq i\leq N-1 $ なるすべての整数 $ i $ について、 $ f\left(\dfrac{S_i}{S_{i+1}}\right)=A_i $ が成り立つ。 - $ \gcd(S_1,S_2,\dots,S_N)=1 $ 数列の **スコア** を、その数列に含まれる要素の総積と定義します。 良い数列の個数は有限個であることが証明できます。良い数列すべてに対するスコアの総和を $ 998244353 $ で割った余りを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ A_2 $ $ \dots $ $ A_{N-1} $

良い数列すべてに対するスコアの総和を $ 998244353 $ で割った余りを出力せよ。

### Sample Explanation 1 例えば $ (2,2,18,9,18,2) $ や $ (18,18,2,1,2,18) $ は良い数列で、スコアはどちらも $ 23328 $ です。 良い数列は全部で $ 16 $ 個存在し、それらすべてに対するスコアの総和は $ 939634344 $ です。 ### Sample Explanation 2 良い数列は $ 2 $ 個存在し、どちらもスコアは $ 9 $ です。 ### Sample Explanation 3 総和を $ 998244353 $ で割った余りを求めることを忘れないでください。 ### Constraints - $ 2\leq N\leq 1000 $ - $ 1\leq A_i\leq 1000 $ $ (1\leq i\leq N-1) $ - 入力はすべて整数