U589462 y.y 华二

zr2322

Ayano 喜欢 GCD。 现在她有一个长度为 $n$ 的数列 $A=\left(a_1, \cdots, a_n\right)$ ，其中 $1 \leq a_i \leq 9$ 。对于其中相邻的两项的 $a_i$ 和 $a_{i+1}$ ，满足 $\operatorname{gcd}\left(a_i, a_{i+1}\right)=1$ 时，Ayano可以通过一次操作交换 $a_i$ 和 $a_{i+1}(1 \leq i \leq n-1)$ 。 请你计算 Ayano 可以通过这个操作得到多少种数列（包含原数列）（mod 998244353）。

第一行一个数 $n$ ，表示数列的长度。 第二行 $n$ 个数，第 $i$ 个数表示 $a_i$ 。

一行一个数表示答案。

$\begin{aligned} & 30 \%: 2 \leq n \leq 10 \\ & \text { 另 } 10 \%: a_i \leq 3 \\ & 100 \%: 2 \leq n \leq 100000,1 \leq a_i \leq 9\end{aligned}$