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.