地災軍団の軍師である黒袍は、エルフの上層部に潜伏していた密偵から神杖に関する情報を得た。彼は奥術宝石に秘められた古代の神秘的な力に強い関心を抱き、数個の奥術宝石を奪取した。そして、地災軍団の首席科学者であるあなたに対し、部下の研究員を率いてその解明に全力を尽くすよう命じた。1ヶ月にわたる苦闘の末、あなたの研究チームは「$2$」型奥術宝石と「$3$」型奥術宝石の内部エネルギー構造を解明した。

これら2種類の構造には一定の類似性がある。内部には $k$ 個の反応コアが存在し、「$2$」型奥術宝石の各コアは $2 \times n$ のグリッド、「$3$」型奥術宝石の各コアは $3 \times n$ のグリッドと見なすことができる（奥術宝石の $k$ と $n$ はそれぞれ異なる可能性がある）。神力反応が始まると、各コアは自動的に神力粒子で満たされる。

形式的に記述すると、各神力粒子は $1 \times 2$ の横置きまたは縦置きのタイルと見なすことができ、コアが満たされるとは、グリッドの各マスがちょうど1つのタイルで覆われることを指す。反応コアを埋める2つの方法において、タイルの配置位置や向きが1箇所でも異なれば、それらは異なる方法と見なす。

例えば、$2 \times 4$ のグリッドを埋める方法は $5$ 通り、$3 \times 2$ のグリッドを埋める方法は $3$ 通り存在する。

奥術宝石の $k$ 個のコアの埋め方がすべて互いに異なる場合、それらは強力な呪術を構成する。黒袍は、ある宝石に対して合計で何種類の異なる呪術が存在するかを知りたがっている（2つの呪術の組み合わせについて、1つ目の呪術の各コア $a$ の埋め方に対して、2つ目の呪術のいずれかのコア $b$ の埋め方が完全に一致するものが存在する場合、これら2つの呪術の組み合わせは同一であると見なす）。

幅が $n$、反応コア数が $k$ である「$2$」型奥術宝石の異なる呪術の数を $F(n,k)$ とし、「$3$」型奥術宝石の異なる呪術の数を $G(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}$ は $998244353$ を法とする $B$ の乗法逆元である。

入力形式

1行目に2つの正整数 $T$ と $m$ が与えられる。それぞれデータセットの数と奥術宝石のタイプ（$2$ または $3$ のみ）を表す。

続く $T$ 行の各行には、3つの正整数 $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}$