Þér er gefin runa af lengd $N$, $A = (A_1, A_2, \dots, A_N)$. Fyrir þessa runu $A$, framkvæmdu eftirfarandi aðgerð í röð fyrir $i = 1, 2, \dots, N - 1$:
- Annaðhvort víxlaðu $A_i$ og $A_{i+1}$, eða gerðu ekkert.
Finndu fjölda ólíkra runa sem geta komið út eftir að þessar aðgerðir hafa verið framkvæmdar, modulo $998244353$.
Inntak
Inntakið er gefið á eftirfarandi sniði:
$$\begin{aligned} &N \\ &A_1 \ A_2 \ \dots \ A_N \end{aligned}$$
- Öll inntök eru heiltölur.
- $1 \le N \le 10^6$
- $1 \le A_i \le N$
Úttak
Prentaðu svarið í einni línu.
Dæmi
Inntak 1
5 1 2 1 2 3
Úttak 1
10
Inntak 2
9 3 1 6 2 2 7 7 6 6
Úttak 2
104
Athugasemd
Í fyrsta dæminu eru $10$ mögulegar runur sem geta komið út eftir að aðgerðirnar hafa verið framkvæmdar. Þessar runur eru:
- $(1, 2, 1, 2, 3)$,
- $(1, 2, 1, 3, 2)$,
- $(1, 2, 2, 1, 3)$,
- $(1, 2, 2, 3, 1)$,
- $(1, 1, 2, 2, 3)$,
- $(1, 1, 2, 3, 2)$,
- $(2, 1, 1, 2, 3)$,
- $(2, 1, 1, 3, 2)$,
- $(2, 1, 2, 1, 3)$,
- $(2, 1, 2, 3, 1)$.