题目描述

对于一个 $1$ 到 $N$ 的排列 $P=(P_1,P_2,\cdots,P_N)$，如下定义 $F(P)$：

• 初始序列 $B=(1,2,\cdots,N)$。只要有一个整数 $i$ 令 $B_i<P_{B_i}$ 存在，就进行下面的操作：

  • 找到最小的满足 $B_j<P_{B_j}$ 的整数 $j$，则将 $B_j$ 替换为 $P_{B_j}$。

  将 $F(P)$ 定义为这一过程结束时的 $B$（可以证明这个过程会在有限步数后终止）。

给你一个长度为 $N$ 的序列 $A=(A_1,A_2,\cdots,A_N)$，请问有多少个 $1$ 到 $N$ 的排列 $P$ 满足 $F(P) = A$？答案对 $998244353$ 取模。

输入格式

第一行一个整数 $N$，接下来 $N$ 个整数 $A_1,A_2,\cdots,A_N$。

输出格式

输出答案，对 $998244353$ 取模。

样例 1 解释

以下用 $\xrightarrow{j}(B_1',B_2',\cdots,B_N')$ 表示选择 $j$ 将 $B_j$ 替换为 $P_{B_j}$ 得到 $(B_1',B_2',\cdots,B_N')$。

选择 $P=(2,3,1,4)$，然后

$$\begin{aligned}(1,2,3,4)&\xrightarrow{1}(2,2,3,4)\\&\xrightarrow{1}(3,2,3,4)\\&\xrightarrow{2}(3,3,3,4)\\\end{aligned}$$

于是 $F((2,3,1,4))=(3,3,3,4)$。

只有这一个 $P$ 满足 $F(P)=(3,3,3,4)$。

样例 1

输入

4
3 3 3 4

输出

1

样例 2

输入

4
2 2 4 3

输出

0

样例 3

输入

8
6 6 8 4 5 6 8 8

输出

18

说明/提示

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq N$
• 所有的输入都是整数。