Le stratège Heipao de la Légion des Désastres Naturels a appris, grâce à des espions infiltrés au sein de l'élite des elfes, des informations sur le Sceptre Divin. Il est très intéressé par l'ancienne puissance mystérieuse contenue dans les gemmes arcaniques. Il a conçu un plan pour dérober plusieurs gemmes arcaniques et vous a ordonné, en tant que scientifique en chef de la Légion, de diriger vos chercheurs pour les décoder. Après un mois d'efforts acharnés, votre équipe de recherche a enfin déchiffré la structure énergétique interne des gemmes arcaniques de type « $2$ » et de type « $3$ ».

Ces deux types de structures présentent une certaine similitude : elles possèdent $k$ cœurs de réaction. Chaque cœur d'une gemme de type « $2$ » peut être considéré comme une grille de $2 \times n$, tandis que chaque cœur d'une gemme de type « $3$ » peut être considéré comme une grille de $3 \times n$. (Notez que les valeurs de $k$ et $n$ peuvent varier selon les gemmes). Lorsque la réaction de puissance divine se produit, chaque cœur est automatiquement rempli de particules divines.

Formellement, chaque particule divine peut être vue comme une tuile de $1 \times 2$ placée horizontalement ou verticalement. Un cœur est considéré comme rempli si chaque case de la grille est exactement recouverte par une tuile. Deux méthodes de remplissage sont considérées comme différentes si la position ou l'orientation d'au moins une tuile diffère.

Par exemple, il existe $5$ façons différentes de remplir une grille de $2 \times 4$ et $3$ façons de remplir une grille de $3 \times 2$.

Si les méthodes de remplissage des $k$ cœurs d'une gemme arcanique sont toutes distinctes, elles se combinent pour former un sortilège puissant. Heipao veut savoir combien de sortilèges différents peuvent être formés pour une gemme donnée (deux combinaisons de sortilèges sont considérées comme identiques si, pour chaque cœur $a$ de la première combinaison, on peut trouver un cœur $b$ de la seconde combinaison tel que les méthodes de remplissage de $a$ et $b$ soient identiques).

Pour une gemme arcanique de type « $2$ » de largeur $n$ et possédant $k$ cœurs, notons le nombre de sortilèges différents $F(n,k)$. Pour une gemme de type « $3$ » de largeur $n$ et possédant $k$ cœurs, notons le nombre de sortilèges différents $G(n,k)$. Par exemple, $F(4,1) = 5, F(4,2) = 10, G(2,2) = 3$.

Le niveau technologique de la Légion des Désastres Naturels ne permet pas de mesurer précisément la longueur $n$ des cœurs de réaction, mais seulement de déterminer une plage approximative $[l, r]$. Vous devez calculer le nombre moyen de sortilèges pour une longueur de cœur dans cet intervalle, c'est-à-dire :

$$\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 le résultat final est sous la forme $\frac{A}{B}$, affichez la valeur de $A \times B^{-1} \bmod 998244353$, où $B^{-1}$ est l'inverse multiplicatif de $B$ modulo $998244353$.

Entrée

La première ligne contient deux entiers positifs $T$ et $m$, représentant respectivement le nombre de cas de test et le type de gemme arcanique (seulement $2$ ou $3$).

Les $T$ lignes suivantes contiennent chacune trois entiers positifs $l, r, k$, représentant la plage de longueur des cœurs et le nombre de cœurs.

Sortie

Pour chaque cas de test, si $m=2$, affichez $\mathrm{ans2}$, sinon si $m=3$, affichez $\mathrm{ans3}$.

Exemples

Entrée 1

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

Sortie 1

665496240
218802505
745517510
133015204
910014966

Entrée 2

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

Sortie 2

3
900767573
52671648
600503426
678428567

Sous-tâches

Pour $100\%$ des données, on a :

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