Problem Statement

For a tree $T$ with $N$ vertices called vertex $1$, vertex $2$, $\ldots$, vertex $N$, let $f(T)$ be the permutation $P$ of $(1,2,\ldots,N)$ obtained by the following procedure.

• Initially, let the sequence $P$ be the empty sequence $()$, and let the set $S$ be $\lbrace1\rbrace$.
• Repeat the following $N$ times.
• Let $x$ be the minimum value of $S$. Remove $x$ from $S$, and append $x$ to the end of $P$.
• Then, let $v_1, v_2, \ldots, v_k$ be the vertices adjacent to vertex $x$ in $T$. For $i=1,2,\ldots,k$, if $v_i$ is not contained in $P$, add $v_i$ to $S$.

You are given a permutation $Q=(Q_1,Q_2,\ldots,Q_N)$ of $(1,2,\ldots,N)$. Find the number, modulo $998244353$, of trees $T$ such that $f(T)=Q$. Here, two trees are distinguished when there exists a pair of vertices $(u,v)$ such that there is an edge between vertex $u$ and vertex $v$ in one tree and there is no edge in the other tree.

Constraints

• $1\le N\le2\times10^5$
• $1\le Q_i\le N\ (1\le i\le N)$
• $Q_i\ne Q_j\ (1\le i\lt j\le N)$
• $Q_1=1$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

• $N$
• $Q_1$ $Q_2$ $\ldots$ $Q_N$

Output

Output the number, modulo $998244353$, of trees $T$ such that $f(T)=Q$.

5
1 3 4 2 5

8

For example, if $T$ is the following tree, then $f(T)=Q$.

The procedure to find $f(T)$ proceeds as shown in the following figure.

Including this tree, the following eight trees satisfy the condition.

Thus, output 8.

20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

868586527

Output modulo $998244353$ the number of trees satisfying the condition.

30
1 16 23 14 18 10 12 21 27 30 17 28 4 9 20 13 22 11 19 3 25 26 6 7 2 8 5 24 15 29

910753763

• Source: AtCoder ABC 478 F