102526: [AtCoder]ABC252 G - Pre-Order

Problem Statement

There is a rooted tree with $N$ vertices called Vertex $1$, $2$, $\ldots$, $N$, rooted at Vertex $1$.

We performed a depth-first search starting at the root and obtained a preorder traversal of the tree: $P_1, P_2, \ldots, P_N$.
During the search, when the current vertex had multiple children, we chose the unvisited vertex with the smallest index.

Find the number of rooted trees consistent with the preorder traversal, modulo $998244353$.
Two rooted trees (with $N$ vertices and rooted at Vertex $1$) are considered different when there is a non-root vertex whose parent is different in the two trees.

Constraints

• $2 \leq N \leq 500$
• $1 \leq P_i\leq N$
• $P_1=1$
• All $P_i$ are distinct.
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$
$P_1$ $P_2$ $\ldots$ $P_N$

Output

Print the number of rooted trees consistent with the preorder traversal, modulo $998244353$.

Sample Input 1

4
1 2 4 3

Sample Output 1

3

The rooted trees consistent with the preorder traversal are the three shown below, so the answer is $3$.

Note that the tree below does not count. This is because, among the children of Vertex $2$, we visit Vertex $3$ before visiting Vertex $4$, resulting in the preorder traversal $1,2,3,4$.

Sample Input 2

8
1 2 3 5 6 7 8 4

Sample Output 2

202