Dany jest ciąg długości $N$, $A = (A_1, A_2, \dots, A_N)$. Dla tego ciągu $A$ wykonaj po kolei dla $i = 1, 2, \dots, N - 1$ następującą operację:
- Zamień miejscami $A_i$ oraz $A_{i+1}$, albo nie rób nic.
Znajdź liczbę różnych ciągów, które mogą powstać po wykonaniu tych operacji, modulo $998244353$.
Wejście
Wejście podawane jest w następującym formacie:
$$\begin{aligned} &N \\ &A_1 \ A_2 \ \dots \ A_N \end{aligned}$$
- Wszystkie dane wejściowe są liczbami całkowitymi.
- $1 \le N \le 10^6$
- $1 \le A_i \le N$
Wyjście
Wypisz odpowiedź w jednym wierszu.
Przykłady
Wejście 1
5 1 2 1 2 3
Wyjście 1
10
Wejście 2
9 3 1 6 2 2 7 7 6 6
Wyjście 2
104
Uwaga
W pierwszym przykładzie istnieje $10$ możliwych ciągów, które mogą powstać po wykonaniu operacji. Ciągi te to:
- $(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)$.