問題背景
真矢： 若你敢抖擞勇气试夺取 我的金杯 向我 展示无上愤怒 的潮水 不随心中 蛰伏洋流暗涌 而摇摆 亦不随月期 涨落 而消退 自瞳孔中 散射出冰长石 的光辉 自胸腔内 颂孤注一掷 娇骜之美 宣战 且往莫退
真矢： 大地 的胸膛在薄纱下 起伏 那是朝晖点亮的国度 展双翅 至空气 稀薄 逐烈日 至璀璨烧灼我 如是说 不沉默 凛冽 的风敲动午夜 的钟 查拉图斯特拉 永恒 这就是我的骄傲 的轮廓
——《誇りと驕り》（日本語訳：水螅、維徳小姐）
本日のテーマは「誇りと驕りのレヴュー」です。
華恋は真矢と戦っています。彼女たちは数直線上に立っています。各ターン、華恋は優勢に立って 1 マス前進する可能性がありますが、多くの場合、彼女は押し戻されます。具体的には、彼女には $k$ 種類の「$a_i$ マス押し戻される」という可能性があります。
戦いの過程で彼女たちが触れた床タイルはすべて破壊されます。華恋が $x$ 番目のマスから $y$ 番目のマスへ押し戻された場合、$y+1$ から $x-1$ までの間のマスは破壊されないことに注意してください。また、彼女たちが最初に立っていたマスも破壊されます。
私（キリン）は、彼女たちが戦いの中で合計で何枚の床タイルを破壊したのか（もちろん、ある位置の床タイルが複数回破壊されても、それは1枚の破壊された床タイルとして数えます）に興味があります。$n$ ターン続くすべての戦闘状況について、それぞれの戦闘状況における破壊された床タイルの枚数の総和を計算してください。答えを $998244353$ で割った余りを求めてください。
わかります！
入力
入力は以下の形式で与えられます。
$n \ k$ $a_1 \ b_1$ $a_2 \ b_2$ $\vdots$ $a_k \ b_k$
出力
答えを出力してください。
入出力例
入力 1
1 1 1 2
出力 1
6
注記
1マス前進する場合と1マス押し戻される場合のどちらであっても、合計で2枚の床タイルが破壊されます。全部で3通りの状況があるため、$2 \times 3 = 6$ となります。
入力 2
20 5 1 2 3 1 5 1 9 2 10 1
出力 2
728464158
制約
すべてのデータにおいて、以下を満たします。
- $1 \le n \le 3 \times 10^6$
- $1 \le k \le 20$
- $1 \le a_i \le n$
- $1 \le b_i < 998244353$
$a_i$ はすべて異なる
テストケース $i$ ($1 \le i \le 10$): $n = 2^i$ を満たす。
- テストケース $11 \sim 14$: $n \le 5 \times 10^4, k \le 5$ を満たす。
- テストケース $15 \sim 17$: $a_i \le 5$ を満たす。
- テストケース $18 \sim 20$: 特殊な制限はない。