Марк откопал где-то у себя на чердаке старый автомат с двумя кнопками, с которым он играл еще в детстве. Игрушка прилично проржавела, но свой функционал продолжает выполнять. При нажатии на первую кнопку на экране появляется один $$$0$$$, а при нажатии на другую, то ли из-за старости, то ли из-за неисправности, автомат выводит сразу $$$k$$$ единиц.
Марку стало интересно, сколько различных строк длины от $$$\ell$$$ до $$$r$$$ можно получить, если автомат при нажатии на вторую кнопку показывает $$$k$$$ единиц. Но так как автомат старый, а интерес у Марка большой, вам предстоит ответить на $$$q$$$ запросов вместо автомата.
Так как ответ на любой запрос Марка может быть очень большим, посчитайте его по модулю $$$998244353$$$
В первой строке вам даны $$$2$$$ целых числа $$$n$$$ и $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$) — ограничение на максимальную длину строки и количество запросов.
В следующих $$$q$$$ строках даны три целых числа $$$\ell_i, \ r_i, \ k_i$$$ ($$$1 \le \ell_i \le r_i \le n, 1 \le k \le n$$$) — диапазон длин и количество единиц, которое печатает автомат.
На каждый запрос выведите количество строк, которые может автомат напечатать по модулю $$$998244353$$$.
| № | Доп. ограничения | Баллы | Необх. группы | Комментарий | ||
| $$$n$$$ | $$$q$$$ | $$$k$$$ | ||||
| $$$0$$$ | — | — | — | — | — | Тесты из условия |
| $$$1$$$ | $$$n \le 15$$$ | $$$q \le 15$$$ | — | $$$7$$$ | $$$0$$$ | — |
| $$$2$$$ | $$$n \le 15$$$ | — | — | $$$9$$$ | $$$0 - 1$$$ | — |
| $$$3$$$ | $$$n \le 5000$$$ | $$$q \le 5000$$$ | — | $$$11$$$ | $$$0 -1$$$ | — |
| $$$4$$$ | $$$n \le 5000$$$ | — | — | $$$8$$$ | $$$0-3$$$ | — |
| $$$5$$$ | — | — | $$$k \le 20$$$ | $$$9$$$ | $$$0-2$$$ | — |
| $$$6$$$ | — | — | — | $$$12$$$ | — | $$$\ell_i = r_i = n$$$ |
| $$$7$$$ | — | — | $$$20 \cdot k \ge n$$$ | $$$13$$$ | — | — |
| $$$8$$$ | $$$n \le 50000$$$ | $$$q \le 50000$$$ | — | $$$21$$$ | $$$0, 1, 3$$$ | — |
| $$$9$$$ | — | — | — | $$$10$$$ | $$$0-8$$$ | — |
8 61 1 14 8 21 8 31 8 14 6 24 6 4
2 81 39 510 26 9
