Гордыня и высокомерие (pride)

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

真矢： 大地 的胸膛在薄纱下 起伏 那是朝晖点亮的国度 展双翅 至空气 稀薄 逐烈日 至璀璨烧灼我 如是说 不沉默 凛冽 的风敲动午夜 的钟 查拉图斯特拉 永恒 这就是我的骄傲 的轮廓 ——《誇りと驕り》（中文填词：水螅、维德小姐）»

Тема сегодняшнего дня — «Ревю гордыни».

Карен сражается с Маю. Они стоят на числовой прямой. В каждом раунде Карен может занять преимущество и продвинуться на одну клетку вперед, но чаще она оказывается отброшенной назад. Конкретнее, у нее есть $k$ типов отступления: в каждом из них она может продвинуться на $a_i$ клеток вперед, а затем быть отброшенной назад на $b_i$ клеток.

В процессе боя все плитки, на которые они наступают, разрушаются. Обратите внимание, что если Карен перемещается из позиции $x$ в позицию $x + a_i$, а затем отбрасывается на позицию $x + a_i - b_i$, то плитки на отрезке $[x, x + a_i]$ и на отрезке $[x + a_i - b_i, x + a_i]$ разрушаются. Начальная клетка, на которой они находились, также разрушается.

Я (Жираф) очень любопытен, сколько всего плиток они разрушили в ходе боя (конечно, если одна и та же плитка была разрушена несколько раз, она все равно считается как одна разрушенная плитка). Пожалуйста, помогите мне вычислить сумму количества разрушенных плиток для всех возможных сценариев боя за $n$ раундов. Вам нужно лишь сообщить мне ответ по модулю $998244353$.

Вакаримасу!

Входные данные

Первая строка содержит целые числа $n$ и $k$.

Далее следуют $k$ строк, в каждой из которых записаны два целых числа $a_i$ и $b_i$, где $a_i$ — количество клеток, на которое Карен продвигается вперед, а $b_i$ — количество клеток, на которое она отбрасывается назад.

Выходные данные

Выведите ответ.

Ограничения

Для $100\%$ данных гарантируется, что $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$ различны.

• Тесты $1 \le i \le 10$: гарантируется $n = 2^i$.
• Тесты $11 \le i \le 14$: гарантируется $n \le 5 \times 10^4, k \le 5$.
• Тесты $15 \le i \le 17$: гарантируется $a_i \le 5$.
• Тесты $18 \le i \le 20$: без дополнительных ограничений.

Примеры

Входные данные 1

1 1
1 2

Выходные данные 1

6

Примечание 1

Независимо от того, продвинулась ли она на $1$ клетку или была отброшена на $1$ клетку, всего было разрушено $2$ плитки, и существует $3$ возможных сценария. Таким образом, $2 \times 3 = 6$.

Входные данные 2

20 5
1 2
3 1
5 1
9 2
10 1

Выходные данные 2

728464158