你正在研究一种名为广度优先搜索（BFS）的图遍历算法。假设你有一个包含 $N$ 个节点（编号从 1 到 $N$）的输入图。该图由邻接矩阵 $M$ 表示，如果 $M_{u,v}$ 为 1，则节点 $u$ 可以遍历到节点 $v$，否则为 0。你的算法将输出 BFS 遍历中节点的访问顺序。该算法的伪代码如下所示。

BFS(M[1..N][1..N]):
    let A be an empty array
    let Q be an empty queue

    append 1 to A
    push 1 to Q

    while Q is not empty:
        pop the front element of Q into u
        for v = 1 to N:
            if M[u][v] == 1 and v is not in A:
                append v to A
                push v to Q

    return A

在研究过程中，你对以下问题感兴趣：给定一个数组 $A$，使得 $A$ 是 1 到 $N$ 的一个排列且 $A_1 = 1$，有多少个包含 $N$ 个节点的简单无向图，其邻接矩阵 $M$ 满足 $\text{BFS}(M) = A$？由于答案可能非常大，请计算答案对 998 244 353 取模的结果。

简单图没有自环（对于 $1 \le i \le N$，$M_{i,i} = 0$），且连接一对节点的边最多只有一条。在无向图中，如果节点 $u$ 与节点 $v$ 相邻，则节点 $v$ 也与节点 $u$ 相邻；形式上，对于 $1 \le u < v \le N$，$M_{u,v} = M_{v,u}$。

如果两个图存在一条边在一个图中存在而在另一个图中不存在，则认为这两个图不同。换句话说，如果两个图的邻接矩阵不同，则认为它们不同。

输入格式

第一行包含一个整数 $N$ ($2 \le N \le 5000$)。

第二行包含 $N$ 个整数 $A_i$。数组 $A$ 是 1 到 $N$ 的一个排列且 $A_1 = 1$。

输出格式

输出一个整数，表示满足 $\text{BFS}(M) = A$ 的包含 $N$ 个节点的简单无向图的数量。由于答案可能非常大，请输出答案对 998 244 353 取模的结果。

样例

输入 1

3
1 2 3

输出 1

3

说明 1

下图展示了所有满足要求的图。

输入 2

3
1 3 2

输出 2

1

说明 2

唯一满足要求的图是包含两条边的图：一条连接节点 1 和 3，另一条连接节点 3 和 2。

输入 3

5
1 3 2 4 5

输出 3

17

输入 4

11
1 2 3 4 5 6 7 8 9 10 11

输出 4

379394847