PTY 得到了一个正整数 $N$ 和一个下标从 $1$ 到 $N$ 的数组 $A$。他需要计算满足以下条件的有序排列对 $(P, Q)$（即 $(P, Q)$ 是一个有序对，其中 $P$ 和 $Q$ 均为 $\{1, 2, \dots, N\}$ 的排列）的总数：
- $M$ 是一个 $N \times N$ 的矩阵，其中 $M_{i,j} = \begin{cases} 1 & \exists k \in \{1, 2, \dots, N\}, i = P_k \land j = Q_k \\ 0 & \text{其他} \end{cases}$。
- 对于每一个 $M_{i,j} = 1$，不存在一个 $(A_j+1) \times (A_j+1)$ 的 $M$ 的子矩阵（即 $M$ 中连续 $(A_j+1)$ 行和 $(A_j+1)$ 列的区域），该子矩阵覆盖了 $M_{i,j}$ 且是一个单位矩阵或单位矩阵的水平镜像。
由于答案可能很大，你只需要告诉 PTY 答案对 $998244353$ 取模的结果。你能帮帮他吗？
输入格式
两行。第一行包含一个整数 $N$ ($1 \le N \le 5000$)。第二行包含 $N$ 个正整数 $A_j$ ($1 \le A_j \le N$)，其中 $j$ 的取值为 $1, 2, \dots, N$。
输出格式
一行，包含答案对 $998244353$ 取模的结果。
样例
样例输入 1
3 1 2 3
样例输出 1
12
样例输入 2
4 4 2 3 2
样例输出 2
432
样例输入 3
5 1 4 4 4 3
样例输出 3
8400