AT_abc478_f [ABC478F] Min-First Search

頂点 $ 1, $ 頂点 $ 2,\ldots, $ 頂点 $ N $ からなる $ N $ 頂点の木 $ T $ に対して、以下の手順で得られる $ (1,2,\ldots,N) $ の順列 $ P $ を $ f(T) $ とします。 - はじめ、列 $ P $ を空列 $ () $ とし、集合 $ S $ を $ \lbrace1\rbrace $ とする。 - 以下を $ N $ 回繰り返す。 - $ S $ の最小値を $ x $ とする。 $ S $ から $ x $ を削除し、 $ P $ の末尾に $ x $ を追加する。 - その後、 $ T $ において頂点 $ x $ に隣接する頂点を頂点 $ v _ 1, $ 頂点 $ v _ 2,\ldots, $ 頂点 $ v _ k $ とする。 $ i=1,2,\ldots,k $ について、 $ P $ に $ v _ i $ が含まれていなければ $ S $ に $ v _ i $ を追加する。 $ (1,2,\ldots,N) $ の順列 $ Q=(Q _ 1,Q _ 2,\ldots,Q _ N) $ が与えられます。 $ f(T)=Q $ となる木 $ T $ の個数を $ 998244353 $ で割った余りを求めてください。 ただし、ふたつの木は、ある頂点の組 $ (u,v) $ が存在して、一方の木では頂点 $ u $ と頂点 $ v $ の間に辺があり、もう一方の木では辺がないとき、区別されます。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ Q _ 1 $ $ Q _ 2 $ $ \ldots $ $ Q _ N $

$ f(T)=Q $ となる木 $ T $ の個数を $ 998244353 $ で割った余りを出力せよ。

### Sample Explanation 1 例えば、以下のような木を $ T $ とすると、 $ f(T)=Q $ となります。  $ f(T) $ を求める手順は以下の図のように進行します。  この木を含めた以下の図のような $ 8 $ つの木が条件を満たします。  よって、`8` を出力してください。 ### Sample Explanation 2 条件を満たす木の個数を $ 998244353 $ で割った余りを出力してください。 ### 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 $ - 入力はすべて整数