32085번 - Count BFS Graph 다국어

문제

You are currently researching a graph traversal algorithm called the Breadth First Search (BFS). Suppose you have an input graph of $N$ nodes (numbered from 1ドル$ to $N$). The graph is represented by an adjacency matrix $M,ドル for which node $u$ can traverse to node $v$ if $M_{u,v}$ is 1ドル,ドル otherwise it is 0ドル$. Your algorithm will output the order the nodes are visited in the BFS. The pseudocode of the algorithm is presented as follows.

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

During your research, you are interested in the following problem. Given an array $A$ such that $A$ is a permutation of 1ドル$ to $N$ and $A_1 = 1$. How many simple undirected graph with $N$ nodes and adjacency matrix $M$ such that $\text{BFS}(M) = A$? Since the answer can be very large, calculate the answer modulo 998ドル,円 244,円 353$.

A simple graph has no self-loop ($M_{i,i} = 0$ for 1ドル ≤ i ≤ N$) and there is at most one edge that connects a pair of nodes. In an undirected graph, if node $u$ is adjacent to node $v,ドル then node $v$ is also adjacent to node $u$; formally, $M_{u,v} = M_{v,u}$ for 1ドル ≤ u < v ≤ N$.

Two graphs are considered different if there is an edge that exists in one graph but not the other. In other words, two graphs are considered different if their adjacency matrices are different.

입력

The first line consists of an integer $N$ (2ドル ≤ N ≤ 5000$).

The second line consists of $N$ integers $A_i$. The array $A$ is a permutation of 1ドル$ to $N$ and $A_1 = 1$.

출력

Output an integer representing the number of simple undirected graphs with $N$ nodes and adjacency matrix $M$ such that $\text{BFS}(M) = A$. Since the answer can be very large, output the answer modulo 998ドル,円 244,円 353$.

제한

힌트