题目描述

存在一棵 $n$ 个点的树，给定序列 $P_n$ 表示树的先序遍历，特别地，已知当一个节点有多个儿子的时候会优先遍历编号较小的儿子。求满足条件的树的方案数。对 $998244353$ 取模。

输入格式

第一行输入 $N$

第二行输入 $P_1$ $P_2$ $\ldots$ $P_N$

输出格式

输出一个整数

4
1 2 4 3

3

8
1 2 3 5 6 7 8 4

202

样例 1 解释

符合前序遍历的有根树如下图所示，因此答案为 $3$ 。

请注意，下面这棵树不算。这是因为在顶点 $2$ 的子顶点中，我们先访问了顶点 $3$ ，然后才访问了顶点 $4$ ，从而产生了前序遍历 $1,2,3,4$ 。

提示

• $2\ \leq\ N\ \leq\ 500$
• $1\ \leq\ P_i\leq\ N$
• $P_1=1$
• $P_i$ 各不相同。