AT_abc450_f [ABC450F] Strongly Connected 2

辺と頂点に番号がついた $ N $ 頂点 $ N-1+M $ 辺の有向グラフがあります。 $ 1 \leq i \leq M $ に対し辺 $ i $ は頂点 $ X_i $ から頂点 $ Y_i $ への有向辺であり、 $ 1 \leq i \leq N-1 $ に対し辺 $ M+i $ は頂点 $ i+1 $ から頂点 $ i $ への有向辺です。 辺 $ 1,2,\dots,M $ のうちいくつか( $ 0 $ 個でもよい) の辺を選ぶ方法は $ 2^M $ 通りありますが、そのうち選んだ辺を削除したあとのグラフが強連結となるものは何通りありますか。 $ 998244353 $ で割った余りを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ X_1 $ $ Y_1 $ $ X_2 $ $ Y_2 $ $ \vdots $ $ X_M $ $ Y_M $

答えを出力せよ。

### Sample Explanation 1 選ぶ辺の番号の集合が $ \{\}, \{1\},\{2\},\{3\},\{2,3\} $ の $ 5 $ 通りのいずれかであるとき、グラフは強連結となります。 ### Sample Explanation 2 与えられるグラフは多重辺を持つことがあります。 ### Constraints - $ 2 \leq N \leq 2\times 10^5 $ - $ 1 \leq M \leq 2\times 10^5 $ - $ 1 \leq X_i < Y_i \leq N $ - 入力は全て整数