Maya:
Jeśli śmiesz zdobyć się na odwagę, by próbować odebrać mój złoty puchar,
Pokażę ci przypływ najwyższego gniewu.
Nie zachwieję się, podążając za ukrytymi prądami w sercu,
Ani nie zniknę wraz z przypływami księżyca.
Z moich źrenic rozprasza się blask skalenia,
Z mojej piersi wyśpiewuję piękno desperackiej dumy.
Wypowiadam wojnę i nie cofnę się.
Maya:
Pierś ziemi faluje pod cienką zasłoną,
To królestwo rozświetlone porannym blaskiem.
Rozwiń skrzydła, aż powietrze stanie się rzadkie,
Goń za palącym słońcem, aż mnie wypali.
Tak mówię, nie milcząc.
Lodowaty wiatr uderza w dzwon północy,
Zaratustra, wieczność.
Oto zarys mojej dumy.
— „誇りと驕り” (tłumaczenie chińskie: Shui Xi, Panna Veder)
Tematem dzisiejszego dnia jest „Revue of Pride”.
Karen walczy z Mayą. Stoją one na osi liczbowej. W każdej rundzie Karen może zyskać przewagę i przesunąć się o jedno pole do przodu, ale częściej bywa odpychana – konkretnie, istnieje $b_i$ możliwości, w których zostaje odepchnięta o $a_i$ pól.
Podczas walki wszystkie płytki, na które trafią, zostają zniszczone. Zauważ, że jeśli Karen zostanie odepchnięta z pola $x$ na pole $y$, to pola pomiędzy $y+1$ a $x-1$ nie zostaną zniszczone. Pola startowe również zostają zniszczone.
Ja (Żyrafa) jestem ciekawy, ile łącznie płytek zniszczyły one podczas walki (oczywiście, płytka w danym miejscu liczona jest jako jedna zniszczona płytka, nawet jeśli została „zniszczona” wielokrotnie). Pomóż mi obliczyć sumę liczby zniszczonych płytek dla wszystkich możliwych przebiegów walki trwających $n$ rund. Podaj wynik modulo $998244353$.
Wakarimasu!
Wejście
W pierwszej linii wejścia znajdują się dwie liczby całkowite $n$ oraz $k$.
Następnie podano $k$ linii, z których każda zawiera dwie liczby całkowite $a_i$ oraz $b_i$.
Wyjście
Wypisz wynik.
Przykład
Wejście 1
1 1 1 2
Wyjście 1
6
Uwagi
W przykładzie 1, niezależnie od tego, czy Karen przesunie się o 1 pole do przodu, czy zostanie odepchnięta o 1 pole, łącznie zniszczone zostają 2 płytki. Istnieją łącznie 3 możliwe sytuacje. Zatem $2 \times 3 = 6$.
Wejście 2
20 5 1 2 3 1 5 1 9 2 10 1
Wyjście 2
728464158
Ograniczenia
Dla 100% danych wejściowych zachodzą warunki: $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 wartości $a_i$ są parami różne.
- Testy $i$ ($1 \le i \le 10$): gwarantowane $n = 2^i$.
- Testy $11 \sim 14$: gwarantowane $n \le 5 \times 10^4$, $k \le 5$.
- Testy $15 \sim 17$: gwarantowane $a_i \le 5$.
- Testy $18 \sim 20$: brak dodatkowych ograniczeń.