El estratega Heipao de la Legión de Desastres Naturales obtuvo información sobre el Cetro de los espías infiltrados en los altos mandos de los elfos, y está muy interesado en el antiguo poder místico contenido en las gemas arcanas. Diseñó un plan para robar varias gemas arcanas y te ordenó, como científico jefe de la Legión, que lideres a tus investigadores para descifrarlas por completo. Tras un mes de arduos intentos, tu equipo de investigación finalmente descifró la estructura energética interna de las gemas arcanas tipo «$2$» y tipo «$3$».

Estas dos estructuras tienen ciertas similitudes: poseen $k$ núcleos de reacción en su interior. Cada núcleo de una gema tipo «$2$» puede verse como una cuadrícula de $2 \times n$, mientras que cada núcleo de una gema tipo «$3$» puede verse como una cuadrícula de $3 \times n$. (Nota: los valores de $k$ y $n$ pueden variar según la gema). Cuando ocurre la reacción de poder divino, cada núcleo se llena automáticamente con partículas de poder divino.

Formalmente, cada partícula de poder divino puede considerarse como una ficha de $1 \times 2$ colocada horizontal o verticalmente. Se define que un núcleo está lleno si cada celda de la cuadrícula está cubierta exactamente por una ficha. Si dos formas de llenar un núcleo difieren en la posición o la orientación de al menos una ficha, se consideran esquemas distintos.

Por ejemplo, hay $5$ formas distintas de llenar una cuadrícula de $2 \times 4$, y $3$ formas distintas de llenar una cuadrícula de $3 \times 2$.

Si las formas de llenado de los $k$ núcleos de una gema arcana son todas distintas entre sí, se combinan para formar un poderoso hechizo. Heipao quiere saber cuántos hechizos distintos existen para una gema determinada (dos combinaciones de hechizos se consideran iguales si, para cada núcleo $a$ en la primera combinación, se puede encontrar un núcleo $b$ en la segunda combinación tal que las formas de llenado de $a$ y $b$ sean idénticas).

Para una gema arcana tipo «$2$» con ancho $n$ y $k$ núcleos de reacción, denotamos el número de hechizos distintos como $F(n,k)$; para una gema tipo «$3$» con ancho $n$ y $k$ núcleos de reacción, denotamos el número de hechizos distintos como $G(n,k)$. Por ejemplo, $F(4,1) = 5, F(4,2) = 10, G(2,2) = 3$.

El nivel tecnológico de la Legión de Desastres Naturales aún no permite medir con precisión la longitud $n$ de los núcleos de reacción, solo se puede determinar un rango aproximado $[l, r]$ para dicha longitud. Debes calcular el número promedio de hechizos para las longitudes de núcleo dentro de este intervalo, es decir:

$$\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)$$

Si la respuesta final tiene la forma $\frac{A}{B}$, imprime el resultado de $A \times B^{-1} \bmod 998244353$, donde $B^{-1}$ es el inverso multiplicativo de $B$ módulo $998244353$.

Entrada

La primera línea contiene dos enteros positivos $T$ y $m$, que representan el número de casos de prueba y el tipo de gema arcana (solo puede ser $2$ o $3$).

Las siguientes $T$ líneas contienen cada una tres enteros positivos $l, r, k$, que representan el rango de longitud de los núcleos y el número de núcleos.

Salida

Para cada caso de prueba, si $m=2$ imprime $\mathrm{ans2}$, y si $m=3$ imprime $\mathrm{ans3}$.

Ejemplos

Entrada 1

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

Salida 1

665496240
218802505
745517510
133015204
910014966

Entrada 2

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

Salida 2

3
900767573
52671648
600503426
678428567

Subtareas

Para el $100\%$ de los datos, se cumple:

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