On vous donne une séquence de longueur $N$, $A = (A_1, A_2, \dots, A_N)$. Pour cette séquence $A$, effectuez l'opération suivante dans l'ordre pour $i = 1, 2, \dots, N - 1$ :
- Soit échanger $A_i$ et $A_{i+1}$, soit ne rien faire.
Trouvez le nombre de séquences distinctes qui peuvent résulter de l'exécution de ces opérations, modulo $998244353$.
Entrée
L'entrée est donnée sous le format suivant :
$$\begin{aligned} &N \\ &A_1 \ A_2 \ \dots \ A_N \end{aligned}$$
- Toutes les entrées sont des entiers.
- $1 \le N \le 10^6$
- $1 \le A_i \le N$
Sortie
Affichez la réponse sur une seule ligne.
Exemples
Entrée 1
5 1 2 1 2 3
Sortie 1
10
Entrée 2
9 3 1 6 2 2 7 7 6 6
Sortie 2
104
Note
Dans le premier exemple, il y a $10$ séquences possibles qui peuvent résulter de l'exécution des opérations. Ces séquences sont :
- $(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)$.