AT_abc435_g [ABC435G] Domino Arrangement

$ 1 $ から $ N $ の番号がついた $ N $ 個のマスがあります。最初、どのマスも色が塗られていません。 $ M $ 種類の色があり、 $ i $ 番目の色ではマス $ L_i,L_i+1,\ldots,R_i $ のうち好きなマスを好きな個数塗ることができます。 以下の条件を満たす色の塗り方は何通りあるか、 $ 998244353 $ で割った余りを求めてください。 - どのマス $ i $ についても、そのマスに色が塗られているならば、マス $ i-1,i+1 $ のうちちょうど一方がマス $ i $ と同じ色で塗られている。 - ただし、マス $ 0,N+1 $ はどの色にも塗られていないとみなす。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ L_1 $ $ R_1 $ $ \vdots $ $ L_M $ $ R_M $

答えを出力せよ。

### Sample Explanation 1 $ 1 $ 番目の色ではマス $ 1,2,3 $ を、 $ 2 $ 番目の色ではマス $ 1,2,3,4,5 $ を塗ることができます。 条件を満たす塗り方は以下の $ 11 $ 通りです。  ### Sample Explanation 2 どのマスにも色を塗らない $ 1 $ 通りが条件を満たします。 ### Sample Explanation 3 $ 998244353 $ で割った余りを求めてください。 ### Constraints - $ 1\leq N,M \leq 5\times 10^5 $ - $ 1\leq L_i \leq R_i \leq N $ - 入力は全て整数