BFS 그래프 개수 세기

너비 우선 탐색(BFS)이라는 그래프 탐색 알고리즘을 연구하고 있다. $1$부터 $N$까지 번호가 매겨진 $N$개의 노드로 이루어진 그래프를 생각하자. 그래프는 인접 행렬 $M$으로 주어지며, $M_{u,v}$가 $1$이면 노드 $u$에서 노드 $v$로 이동할 수 있고, 그렇지 않으면 $M_{u,v}$는 $0$이다. 이 알고리즘은 노드를 방문한 순서를 출력한다.

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

$1$부터 $N$까지의 순열이고 $A_1 = 1$인 배열 $A$가 주어진다. $\text{BFS}(M) = A$를 만족하는 $N$개의 노드를 가진 단순 무방향 그래프의 인접 행렬 $M$의 개수를 구하라. 답은 $998\,244\,353$으로 나눈 나머지를 출력한다.

단순 그래프는 자기 루프가 없고($M_{i,i} = 0$, $1 \le i \le N$), 두 노드를 잇는 간선은 최대 하나이다. 무방향 그래프에서는 $1 \le u < v \le N$인 모든 $u, v$에 대해 $M_{u,v} = M_{v,u}$이다. 인접 행렬이 다르면 서로 다른 그래프로 본다.

첫 줄에 정수 $N$ ($2 \le N \le 5000$)이 주어진다.

둘째 줄에 정수 $A_i$가 $N$개 주어진다. 배열 $A$는 $1$부터 $N$까지의 순열이며, $A_1 = 1$이다.

$\text{BFS}(M) = A$를 만족하는 $N$개의 노드를 가진 단순 무방향 그래프의 개수를 $998\,244\,353$으로 나눈 나머지를 출력한다.