题目描述

对于一棵有 $N$ 个顶点、分别称为顶点 $1$、顶点 $2$、$\ldots$、顶点 $N$ 的树 $T$，定义 $f(T)$ 为按以下步骤得到的 $(1,2,\ldots,N)$ 的排列 $P$。

• 首先，令序列 $P$ 为空序列 $()$，令集合 $S$ 为 $\lbrace1\rbrace$。
• 重复以下操作 $N$ 次。
• 令 $x$ 为 $S$ 中的最小值。从 $S$ 中删去 $x$，并把 $x$ 追加到 $P$ 的末尾。
• 然后，令 $v_1, v_2, \ldots, v_k$ 为 $T$ 中与顶点 $x$ 相邻的顶点。对于 $i=1,2,\ldots,k$，若 $v_i$ 不包含在 $P$ 中，则把 $v_i$ 加入 $S$。

给定 $(1,2,\ldots,N)$ 的排列 $Q=(Q_1,Q_2,\ldots,Q_N)$。请求出满足 $f(T)=Q$ 的树 $T$ 的个数模 $998244353$ 的值。这里，当存在一对顶点 $(u,v)$ 使得其中一棵树的顶点 $u$ 与顶点 $v$ 之间有边、而另一棵树中没有时，就认为这两棵树不同。

输入格式

输入按以下格式从标准输入读入：

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

输出格式

输出满足 $f(T)=Q$ 的树 $T$ 的个数模 $998244353$ 的值。

5
1 3 4 2 5

8

例如，若 $T$ 为如下图所示的树，则 $f(T)=Q$。

求 $f(T)$ 的步骤如下图所示。

包含这棵树在内，共有如下图所示的 $8$ 棵树满足条件。

因此输出 8。

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

868586527

输出满足条件的树的个数模 $998244353$ 的值。

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

数据范围

• $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$

• 输入均为整数。

• 来源：AtCoder ABC 478 F

子任务设置

• 子任务 1（30 分）：$N \le 2000$。
• 子任务 2（30 分）：$N \le 10^4$。
• 子任务 3（40 分）：无特殊限制。