AT_awtf2025_b Movies

maroon くんの夏休みは Day $ 1 $ から Day $ N $ までの $ N $ 日間あります． また夏休み期間中には， $ 1 $ から $ M $ までの番号のついた $ M $ 本の映画の上映が予定されており，映画 $ i $ は Day $ L_i $ から Day $ R_i $ まで見られます． 映画全体の部分集合 $ s $ に対し， $ f(s) $ を以下のように定義します． - maroon くんが $ 1 $ 日に $ 1 $ 本以下の映画を見られるとき，夏休みを通して見られる $ s $ 内の映画の本数の最大値を $ f(s) $ とする． なお，同じ映画を複数回見てもそれは $ 1 $ 本とカウントするものとする． $ s $ としてあり得る集合は $ 2^M $ 通りあります． それら全てに対する $ f(s) $ の総和を $ 998244353 $ で割ったあまりを求めてください．

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

答えを出力せよ．

### Sample Explanation 1 ほとんどの $ s $ に対して， $ f(s)=|s| $ が成り立ちます． 唯一の例外は $ s=\{1,2,3\} $ で，このとき $ f(s)=2 $ となります． すべての $ s $ に対する $ f(s) $ の総和は $ 11 $ です． ### Constraints - $ 1 \leq N \leq 100 $ - $ 1 \leq M \leq N \times (N+1) /2 $ - $ 1 \leq L_i \leq R_i \leq N $ - $ (L_i,R_i) \neq (L_j,R_j) $ ( $ i \neq j $ ) - 入力はすべて整数