Problem Description

The strategist of the Earthquake Legion, Black Robe, has obtained intelligence about the divine staff from a spy embedded in the high ranks of the elves. He is very interested in the ancient mysterious power contained within the arcane gems. He has designed a plan to seize several arcane gems and ordered you, the chief scientist of the Earthquake Legion, to lead your research team in cracking their internal energy structures. After a month of arduous attempts, your team has finally deciphered the internal energy structures of the "2" type and "3" type arcane gems.

These two types of structures share certain similarities. They both have $k$ reaction cores. Each core of the "2" type arcane gem can be seen as a $2 \times n$ grid, while each core of the "3" type arcane gem can be seen as a $3 \times n$ grid. (Note that $k$ and $n$ may differ for different gems) When the divine reaction occurs, each core is automatically filled with divine particles.

Formally described, each divine particle can be seen as a $1 \times 2$ horizontal or vertical square. The core is considered filled if every grid is exactly covered by one square. If there is a difference in the position or orientation of a square between two filled core schemes, they are considered different.

For example, there are 5 different ways to fill a $2 \times 4$ grid, and 3 different ways to fill a $3 \times 2$ grid.

If the filling methods of the $k$ cores in an arcane gem are all different, they will combine to form a powerful spell. Black Robe wants to know how many different spells are possible for a given gem (For two spell combinations, if each core $a$ in the first spell can find a core $b$ in the second spell such that $a$ and $b$ have the same filling method, then these two spell combinations are considered the same).

For a "2" type arcane gem with width $n$ and $k$ reaction cores, let the number of different spells be $F(n,k)$; for a "3" type arcane gem with width $n$ and $k$ reaction cores, let the number of different spells be $G(n,k)$. For example, $F(4,1) = 5$, $F(4,2) = 10$, $G(2,2) = 3$.

The technology of the Earthquake Legion cannot accurately measure the length $n$ of the reaction cores, only determining the approximate range $[l,r]$. You need to calculate the average number of spells for core lengths within this range, i.e.,

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

Let the final answer be in the form $\frac{A}{B}$, output the result of $A \times B^{-1} \bmod 998244353$, where $B^{-1}$ is the multiplicative inverse of $B$ modulo $998244353$.

Input Format

The first line contains two positive integers $T$ and $m$, representing the number of data sets and the type of arcane gem (either 2 or 3).

The next $T$ lines each contain three positive integers $l, r, k$, representing the range of core lengths and the number of cores.

Output Format

For each data set, if $m=2$ output $ans2$, if $m=3$ output $ans3$.

Sample Input and Output

Input Sample #1

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

Output Sample #1

665496240
218802505
745517510
133015204
910014966

Input Sample #2

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

Output Sample #2

3
900767573
52671648
600503426
678428567

Notes/Hints

For all data, it is guaranteed that $r-l+1$ is not a multiple of $998244353$.

Due to the slow computers in the exam room, the problem setter has changed the data so that all $T=1$.

Note: The data range is incorrect; it actually satisfies $1 \leq l \leq r \leq 6 \times 10^{18}$.

见题面 Input 部分

见题面 Output 部分