Heipao, the strategist of the Disaster Legion, learned about the Scepter from a spy embedded in the high ranks of the Elves. He was deeply interested in the ancient, mysterious power contained within the Arcane Gems. He orchestrated the theft of several Arcane Gems and ordered you, the chief scientist of the Disaster Legion, to lead your researchers in fully deciphering them. After a month of arduous attempts, your research team finally cracked the internal energy structures of the "Type 2" and "Type 3" Arcane Gems.

These two types of structures share certain similarities. They contain $k$ reaction cores. Each core of a "Type 2" Arcane Gem can be viewed as a $2 \times n$ grid, while each core of a "Type 3" Arcane Gem can be viewed as a $3 \times n$ grid. (Note that $k$ and $n$ may differ between Arcane Gems.) When the divine power reaction occurs, each core is automatically filled with divine power particles.

Formally, each divine power particle can be viewed as a $1 \times 2$ horizontal or vertical tile. A core is considered "filled" if every grid cell is covered by exactly one tile. Two ways of filling a reaction core are considered different if there is any difference in the position or orientation of at least one tile.

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 of an Arcane Gem are all distinct, they combine to form a powerful spell. Heipao wants to know how many different spells exist for a given gem. (Two spell combinations are considered the same if, for every core $a$ in the first spell, there exists a core $b$ in the second spell such that the filling method of $a$ and $b$ are identical.)

For a "Type 2" Arcane Gem with width $n$ and $k$ reaction cores, let the number of different spells be $F(n, k)$. For a "Type 3" 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 Disaster Legion's technology cannot precisely measure the length $n$ of the reaction cores; it can only determine that the length falls within the range $[l, r]$. You need to calculate the average number of spells for reaction core lengths within this interval, which is:

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

Express the final answer as $\frac{A}{B}$ and output the result of $A \times B^{-1} \bmod 998244353$, where $B^{-1}$ is the modular multiplicative inverse of $B$ modulo $998244353$.

Input

The first line contains two positive integers $T$ and $m$, representing the number of test cases and the type of Arcane Gem (only $2$ or $3$ are possible).

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

Output

For each test case, if $m=2$, output $\mathrm{ans2}$; if $m=3$, output $\mathrm{ans3}$.

Examples

Input 1

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

Output 1

665496240
218802505
745517510
133015204
910014966

Input 2

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

Output 2

3
900767573
52671648
600503426
678428567

Subtasks

For $100\%$ of the data:

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