分数: 600 点
问题陈述
有一棵有根的树 N 名为 Vertex 的顶点 1, 2, \ldots, N,植根于 Vertex 1.
我们从根开始执行深度优先搜索,并获得树的前序遍历: P_1, P_2, \ldots, P_N.
在搜索过程中,当当前顶点有多个子节点时,我们选择索引最小的未访问顶点。
什么是前序遍历?
我们从根开始并重复以下过程来列出树的顶点。
如果当前顶点 u 尚未记录,记录一下。
那么,如果 u 有一个未访问的顶点,请转到该顶点。
否则,终止如果 u 是根,转到父级 u 如果不是。
这里记录的顶点列表就是树的前序遍历。
求与前序遍历一致的有根树的数量,取模 998244353.
两棵有根树( N 顶点并以 Vertex 为根
当两棵树中存在父节点不同的非根顶点时, 1) 被认为是不同的。
约束
- 2 \leq N \leq 500
- 1 \leq P_i\leq N
- P_1=1
- 全部 P_i 是不同的。
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N P_1 P_2 \ldots P_N
输出
打印与前序遍历一致的有根树的数量,取模 998244353.
示例输入 1
4 1 2 4 3
示例输出 1
3
与先序遍历一致的有根树是下图所示的三个,所以答案是 3.

请注意,下面的树不算数。这是因为,Vertex 的孩子们中 2,我们访问Vertex 3 访问 Vertex 之前 4,导致先序遍历 1,2,3,4.

示例输入 2
8 1 2 3 5 6 7 8 4
示例输出 2
202