/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 600 点
問題文
正の有理数 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 で割った余りを求めてください。
制約
- 2\leq N\leq 1000
- 1\leq A_i\leq 1000 (1\leq i\leq N-1)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N
A_1 A_2 \dots A_{N-1}
出力
良い数列すべてに対するスコアの総和を 998244353 で割った余りを出力せよ。
入力例 1
6 1 9 2 2 9
出力例 1
939634344
例えば (2,2,18,9,18,2) や (18,18,2,1,2,18) は良い数列で、スコアはどちらも 23328 です。
良い数列は全部で 16 個存在し、それらすべてに対するスコアの総和は 939634344 です。
入力例 2
2 9
出力例 2
18
良い数列は 2 個存在し、どちらもスコアは 9 です。
入力例 3
25 222 299 229 22 999 922 99 992 22 292 222 229 992 922 22 992 222 222 99 29 92 999 2 29
出力例 3
192457116
総和を 998244353 で割った余りを求めることを忘れないでください。
Score : 600 points
Problem Statement
For a positive rational number x, define f(x) as follows:
Express x as \dfrac{P}{Q} using coprime positive integers P and Q. f(x) is defined as the value P\times Q.
You are given a positive integer N and a sequence A=(A_1,A_2,\dots,A_{N-1}) of positive integers of length N-1.
We call a sequence S=(S_1,S_2,\dots,S_N) of positive integers of length N a good sequence if it satisfies all of the following conditions:
- For every integer i with 1\leq i\leq N-1, it holds that f\left(\dfrac{S_i}{S_{i+1}}\right)=A_i.
- \gcd(S_1,S_2,\dots,S_N)=1.
Define the score of a sequence as the product of all its elements.
It can be proved that there are finitely many good sequences. Find the sum, modulo 998244353, of the scores of all good sequences.
Constraints
- 2\leq N\leq 1000
- 1\leq A_i\leq 1000 (1\leq i\leq N-1)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N
A_1 A_2 \dots A_{N-1}
Output
Print the sum, modulo 998244353, of the scores of all good sequences.
Sample Input 1
6 1 9 2 2 9
Sample Output 1
939634344
For example, both (2,2,18,9,18,2) and (18,18,2,1,2,18) are good sequences, and both have a score of 23328.
There are a total of 16 good sequences, and the sum of the scores of all of them is 939634344.
Sample Input 2
2 9
Sample Output 2
18
There are 2 good sequences, both with a score of 9.
Sample Input 3
25 222 299 229 22 999 922 99 992 22 292 222 229 992 922 22 992 222 222 99 29 92 999 2 29
Sample Output 3
192457116
Do not forget to compute the sum modulo 998244353.