You are given a sequence of length $N$, $A = (A_1, A_2, \dots, A_N)$. For this sequence $A$, perform the following operation in order for $i = 1, 2, \dots, N - 1$:
- Either swap $A_i$ and $A_{i+1}$, or do nothing.
Find the number of distinct sequences that can result after performing these operations, modulo $998244353$.
Input
The input is given in the following format:
$$\begin{aligned} &N \\ &A_1 \ A_2 \ \dots \ A_N \end{aligned}$$
- All inputs are integers.
- $1 \le N \le 10^6$
- $1 \le A_i \le N$
Output
Print the answer in a single line.
Examples
Input 1
5 1 2 1 2 3
Output 1
10
Input 2
9 3 1 6 2 2 7 7 6 6
Output 2
104
Note
In the first example, there are $10$ possible sequences that can result after performing the operations. These sequences are:
- $(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)$.