地災軍團的軍師黑袍從潛伏在精靈高層的密探手中得知了神杖的情報，他對奧術寶石中蘊含的遠古神秘力量十分感興趣。他設計奪取了數塊奧術寶石，並命令作為地災軍團首席科學家的你帶領手下的研究人員全力破解。經過了一個月的艱苦嘗試，你的研究團隊終於破譯了 「$2$」型奧術寶石和 「$3$」型奧術寶石的內部能量結構。

這兩類結構有著一定的相似性，它們的內部具有 $k$ 個反應核心，「$2$」型奧術寶石的每個核心都可以看成是一個 $2 \times n$ 的網格，而 「$3$」型奧術寶石的每個核心都可以看成是一個 $3 \times n$ 的網格。（注意奧術寶石的 $k$ 和 $n$ 可能不同）當神力反應進行時，每個核心自動填充滿神力顆粒。

形式化地描述，每個神力顆粒可以看成是一個 $1 \times 2$ 橫置或豎置的方格，核心填滿的定義為每個網格都恰好被一個方格覆蓋。若在兩種填滿反應核心的方案中存在一個方格放置的位置或方式不同，就認為方案不同。

如填滿 $2 \times 4$ 的網格有 $5$ 種不同的方案，填滿 $3 \times 2$ 的網格有 $3$ 種不同的方案。

如果奧術寶石的 $k$ 個核心的填充方式互不相同，它們就會組合出強大的咒術。黑袍想知道對於某個寶石一共有多少種不同的咒術（對於兩種咒術組合，如果第一種咒術中每個核心 $a$ 的填充方式都可以找到第二種咒術的某個核心 $b$，使得 $a$ 和 $b$ 的填充方式完全相同，則認為這兩種咒術組合相同）。

對於寬度為 $n$、反應核心個數為 $k$ 的 「$2$」型奧術寶石，設不同的咒術為 $F(n,k)$；對於寬度為 $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}$ 是 $B$ 在 $998244353$ 下的乘法逆元。

輸入格式

第一行為兩個正整數 $T$、$m$ ，表示資料組數和奧術寶石的類型（只可能為 $2$ 或 $3$ ）。

接下來 $T$ 行每行三個正整數 $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}$