Czarny Szat, strateg Legionu Katastrofy, dowiedział się od szpiegów infiltrujących wyższe sfery elfów o istnieniu Kostura i zainteresował się starożytną, tajemniczą mocą zawartą w klejnotach arkana. Zaprojektował plan kradzieży kilku takich klejnotów i rozkazał tobie, głównemu naukowcowi Legionu, poprowadzić zespół badawczy w celu ich złamania. Po miesiącu ciężkich prób twój zespół w końcu rozszyfrował wewnętrzną strukturę energetyczną klejnotów arkana typu „$2$” oraz typu „$3$”.

Oba typy struktur wykazują pewne podobieństwo: posiadają $k$ rdzeni reakcyjnych. Każdy rdzeń klejnotu typu „$2$” można postrzegać jako siatkę $2 \times n$, natomiast każdy rdzeń klejnotu typu „$3$” jako siatkę $3 \times n$. (Uwaga: wartości $k$ oraz $n$ mogą być różne dla różnych klejnotów). Podczas reakcji mocy, każdy rdzeń jest automatycznie wypełniany cząstkami mocy.

Formalnie, każdą cząstkę mocy można postrzegać jako płytkę $1 \times 2$ ułożoną poziomo lub pionowo. Wypełnienie rdzenia definiuje się jako sytuację, w której każda komórka siatki jest dokładnie przykryta jedną płytką. Dwa sposoby wypełnienia rdzenia uważa się za różne, jeśli istnieje choć jedna płytka, której położenie lub orientacja jest inna.

Na przykład, istnieje $5$ różnych sposobów wypełnienia siatki $2 \times 4$ oraz $3$ sposoby wypełnienia siatki $3 \times 2$.

Jeśli sposoby wypełnienia $k$ rdzeni klejnotu są wzajemnie różne, tworzą one potężne zaklęcie. Czarny Szat chce wiedzieć, ile różnych zaklęć można utworzyć dla danego klejnotu (dwa zestawy zaklęć uważa się za identyczne, jeśli dla każdego rdzenia $a$ w pierwszym zestawie można znaleźć rdzeń $b$ w drugim zestawie, taki że sposób wypełnienia $a$ i $b$ jest całkowicie identyczny).

Dla klejnotu typu „$2$” o szerokości $n$ i liczbie rdzeni $k$, niech liczba różnych zaklęć wynosi $F(n,k)$. Dla klejnotu typu „$3$” o szerokości $n$ i liczbie rdzeni $k$, niech liczba różnych zaklęć wynosi $G(n,k)$. Na przykład $F(4,1) = 5, F(4,2) = 10, G(2,2) = 3$.

Poziom technologiczny Legionu Katastrofy nie pozwala na precyzyjny pomiar długości rdzenia $n$, a jedynie na określenie przybliżonego zakresu $[l, r]$. Musisz obliczyć średnią liczbę zaklęć dla długości rdzenia w tym przedziale, czyli:

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

Przyjmując, że ostateczny wynik ma postać $\frac{A}{B}$, wyprowadź wynik $A \times B^{-1} \bmod 998244353$, gdzie $B^{-1}$ jest odwrotnością modularną $B$ w ciele $998244353$.

Wejście

Pierwsza linia zawiera dwie dodatnie liczby całkowite $T$ oraz $m$, oznaczające liczbę zestawów danych oraz typ klejnotu (tylko $2$ lub $3$).

Następnie $T$ linii, każda zawiera trzy dodatnie liczby całkowite $l, r, k$, oznaczające zakres długości rdzenia oraz liczbę rdzeni.

Wyjście

Dla każdego zestawu danych, jeśli $m=2$, wyprowadź $\mathrm{ans2}$, a jeśli $m=3$, wyprowadź $\mathrm{ans3}$.

Przykład

Przykład 1

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

Wyjście 1

665496240
218802505
745517510
133015204
910014966

Przykład 2

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

Wyjście 2

3
900767573
52671648
600503426
678428567

Podzadania

Dla $100\%$ danych spełnione są warunki:

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