Стратег Легиона Бедствий, Черная Мантия, узнал от шпионов, внедренных в высшие эшелоны эльфов, информацию о Жезле и заинтересовался древней мистической силой, заключенной в магических кристаллах. Он спланировал захват нескольких таких кристаллов и приказал вам, как главному ученому Легиона Бедствий, вместе с подчиненными исследователями приложить все усилия для их расшифровки. После месяца упорных попыток ваша исследовательская группа наконец расшифровала внутреннюю энергетическую структуру магических кристаллов типа «$2$» и типа «$3$».

Эти два типа структур обладают определенным сходством: внутри них находится $k$ реакционных ядер. Каждое ядро кристалла типа «$2$» можно представить как сетку $2 \times n$, а каждое ядро кристалла типа «$3$» — как сетку $3 \times n$. (Заметьте, что значения $k$ и $n$ для кристаллов могут различаться). Когда происходит реакция божественной силы, каждое ядро автоматически заполняется частицами божественной силы.

Формально, каждую частицу божественной силы можно представить как плитку размером $1 \times 2$, расположенную горизонтально или вертикально. Заполнение ядра означает, что каждая клетка сетки оказывается в точности покрыта одной плиткой. Если в двух способах заполнения реакционного ядра хотя бы одна плитка расположена иначе, то такие способы считаются различными.

Например, существует $5$ различных способов заполнения сетки $2 \times 4$ и $3$ различных способа заполнения сетки $3 \times 2$.

Если способы заполнения $k$ ядер магического кристалла попарно различны, они образуют мощное заклинание. Черная Мантия хочет знать, сколько всего различных комбинаций заклинаний существует для данного кристалла (две комбинации заклинаний считаются одинаковыми, если для каждого ядра $a$ в первой комбинации можно найти такое ядро $b$ во второй комбинации, что способы их заполнения полностью совпадают).

Пусть $F(n,k)$ — количество различных заклинаний для магического кристалла типа «$2$» с шириной $n$ и $k$ реакционными ядрами; пусть $G(n,k)$ — количество различных заклинаний для магического кристалла типа «$3$» с шириной $n$ и $k$ реакционными ядрами. Например, $F(4,1) = 5, F(4,2) = 10, G(2,2) = 3$.

Технологический уровень Легиона Бедствий пока не позволяет точно измерить длину $n$ реакционного ядра, можно лишь определить примерный диапазон $[l, r]$. Вам необходимо вычислить среднее количество заклинаний для длин ядер в этом диапазоне, то есть:

$$\mathrm{ans2} = \frac{1}{r-l+1}\sum_{n=l}^{r} F(n,k)$$

$$\mathrm{ans3} = \frac{1}{r-l+1}\sum_{n=l}^{r} G(n,k)$$

Представьте итоговый ответ в виде $\frac{A}{B}$ и выведите результат $A \times B^{-1} \bmod 998244353$, где $B^{-1}$ — мультипликативная инверсия $B$ по модулю $998244353$.

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

В первой строке содержатся два целых положительных числа $T$ и $m$, обозначающие количество наборов данных и тип магического кристалла (может быть только $2$ или $3$).

Далее следуют $T$ строк, каждая из которых содержит три целых положительных числа $l, r, k$, обозначающие диапазон длин ядер и количество ядер.

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

Для каждого набора данных, если $m=2$, выведите $\mathrm{ans2}$, если $m=3$, выведите $\mathrm{ans3}$.

Примеры

Пример 1

5 2
2 4 2
1 10000 501
52501 233333333333 1
52501 233333333333 2
52501 233333333333 50

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

665496240
218802505
745517510
133015204
910014966

Пример 2

5 3
2 2 2
1 10000 501
52501 233333333333 1
52501 233333333333 2
52501 233333333333 50

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

3
900767573
52671648
600503426
678428567

Подзадачи

Для $100\%$ данных выполняются условия:

• $T=1$
• $1\le l\le r\le 10^{18}$
• $1\le k \le 501$
• $r - l + 1 \not \equiv 0 \pmod {998244353}$