前序遍历

题目描述

有一棵包含 $N$ 个顶点、以顶点 $1$ 为根的有根树，顶点编号为 $1, 2, \ldots, N$。

我们从根开始进行一次深度优先搜索，得到树的前序遍历：$P_1, P_2, \ldots, P_N$。

在搜索过程中，当当前顶点有多个子顶点时，我们选择编号最小的未访问顶点。

什么是前序遍历？

从根开始，重复以下过程来列出树的顶点。

如果当前顶点 $u$ 尚未被记录，则记录它。

然后，如果 $u$ 有未访问的顶点，则前往该顶点。

否则，如果 $u$ 是根则结束，如果不是根则前往 $u$ 的父顶点。

按此顺序记录的顶点列表即为树的前序遍历。

求与前序遍历一致的有根树的个数，结果对 $998244353$ 取模。

两棵有根树（各有 $N$ 个顶点且以顶点 $1$ 为根）在存在某个非根顶点在两棵树中的父顶点不同时视为不同。

输入格式

输入按以下格式从标准输入给出：

N
P_1 P_2 … P_N

输出格式

打印与前序遍历一致的有根树的个数，对 $998244353$ 取模。

样例

4
1 2 4 3

3

与前序遍历一致的有根树是下面所示的 3 棵，因此答案为 $3$。

注意下面这棵树不计入。这是因为在顶点 2 的子顶点中，我们先访问顶点 3 再访问顶点 4，得到前序遍历 $1, 2, 3, 4$。

8
1 2 3 5 6 7 8 4

202

数据范围

• $2 \le N \le 500$
• $1 \le P_i \le N$
• $P_1 = 1$
• 所有 $P_i$ 互不相同。
• 输入中的所有值均为整数。