AT_abc478_f [ABC478F] Min-First Search

For a tree $ T $ with $ N $ vertices called vertex $ 1 $ , vertex $ 2 $ , $ \ldots $ , vertex $ N $ , let $ f(T) $ be the permutation $ P $ of $ (1,2,\ldots,N) $ obtained by the following procedure. - Initially, let the sequence $ P $ be the empty sequence $ () $ , and let the set $ S $ be $ \lbrace1\rbrace $ . - Repeat the following $ N $ times. - Let $ x $ be the minimum value of $ S $ . Remove $ x $ from $ S $ , and append $ x $ to the end of $ P $ . - Then, let $ v_1, v_2, \ldots, v_k $ be the vertices adjacent to vertex $ x $ in $ T $ . For $ i=1,2,\ldots,k $ , if $ v _ i $ is not contained in $ P $ , add $ v _ i $ to $ S $ . You are given a permutation $ Q=(Q _ 1,Q _ 2,\ldots,Q _ N) $ of $ (1,2,\ldots,N) $ . Find the number, modulo $ 998244353 $ , of trees $ T $ such that $ f(T)=Q $ . Here, two trees are distinguished when there exists a pair of vertices $ (u,v) $ such that there is an edge between vertex $ u $ and vertex $ v $ in one tree and there is no edge in the other tree.

The input is given from Standard Input in the following format: > $ N $ $ Q _ 1 $ $ Q _ 2 $ $ \ldots $ $ Q _ N $

Output the number, modulo $ 998244353 $ , of trees $ T $ such that $ f(T)=Q $ .

### Sample Explanation 1 For example, if $ T $ is the following tree, then $ f(T)=Q $ .  The procedure to find $ f(T) $ proceeds as shown in the following figure.  Including this tree, the following eight trees satisfy the condition.  Thus, output `8`. ### Sample Explanation 2 Output modulo $ 998244353 $ the number of trees satisfying the condition. ### Constraints - $ 1\le N\le2\times10 ^ 5 $ - $ 1\le Q _ i\le N\ (1\le i\le N) $ - $ Q _ i\ne Q _ j\ (1\le i\lt j\le N) $ - $ Q _ 1=1 $ - All input values are integers.