Count BFS Graph

You are researching a graph traversal algorithm called Breadth First Search (BFS). Suppose you have a graph with $N$ nodes numbered from $1$ to $N$. The graph is given as an adjacency matrix $M$, where node $u$ can traverse to node $v$ if $M_{u,v}$ is $1$, and otherwise $M_{u,v}$ is $0$. The algorithm outputs the order in which nodes are visited.

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

Given an array $A$ that is a permutation of $1$ to $N$ with $A_1 = 1$, count the simple undirected graphs with $N$ nodes whose adjacency matrix $M$ satisfies $\text{BFS}(M) = A$. Output the count modulo $998\,244\,353$.

A simple graph has no self-loops ($M_{i,i} = 0$ for $1 \le i \le N$), and each pair of nodes is connected by at most one edge. In an undirected graph, $M_{u,v} = M_{v,u}$ for $1 \le u < v \le N$. Two graphs are different if their adjacency matrices differ.

The first line contains an integer $N$ ($2 \le N \le 5000$).

The second line contains $N$ integers $A_i$. The array $A$ is a permutation of $1$ to $N$, and $A_1 = 1$.

Print the number of simple undirected graphs with $N$ nodes whose adjacency matrix $M$ satisfies $\text{BFS}(M) = A$, modulo $998\,244\,353$.