問題背景

真矢： 若你敢抖擞勇气试夺取 我的金杯 向我 展示无上愤怒 的潮水 不随心中 蛰伏洋流暗涌 而摇摆 亦不随月期 涨落 而消退 自瞳孔中 散射出冰长石 的光辉 自胸腔内 颂孤注一掷 娇骜之美 宣战 且往莫退

真矢： 大地 的胸膛在薄纱下 起伏 那是朝晖点亮的国度 展双翅 至空气 稀薄 逐烈日 至璀璨烧灼我 如是说 不沉默 凛冽 的风敲动午夜 的钟 查拉图斯特拉 永恒 这就是我的骄傲 的轮廓

——《誇りと驕り》（中文填词：水螅、维德小姐）

本日的主题是「骄傲のRevue」。

华恋在与真矢战斗。她们站在一条数轴上。每个回合，华恋可能占据上风并前进 1 格，但更多的时候是被击退，具体的，她还有 $k$ 种可能被击退 $a_i$ 格。

在交手过程中她们所碰到的地砖都会被破坏。请注意如果华恋从第 $x$ 格被击退到 $y$ 格，那么 $y+1 \sim x-1$ 中间的格子并不会被破坏。她们起始时的格子也会被破坏。

我（长颈鹿）很好奇她们在战斗中总共破坏了多少块地砖（当然一个位置的地砖就算被破坏多次也只是一块被破坏的地砖），请你帮我计算一下对于发生 $n$ 个回合的所有情况，每种战斗情况的破坏地砖数求和。你只用告诉我答案同余 $998244353$ 的结果就行了。

哇嘎利马斯！

输入

第一行输入正整数 $n, k$。

接下来共 $k$ 行，每行输入两个正整数 $a_i, b_i$。

输出

输出答案。

入出力例

入力 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$: 无特殊限制。