Quân sư Hắc Bào của Quân đoàn Thảm họa đã biết được thông tin về cây quyền trượng từ các mật thám cài cắm trong tầng lớp cấp cao của tộc Tiên. Ông ta vô cùng hứng thú với sức mạnh huyền bí cổ xưa ẩn chứa trong các viên ngọc Arcane. Hắc Bào đã thiết kế và chiếm đoạt được một vài viên ngọc Arcane, đồng thời ra lệnh cho bạn, với tư cách là nhà khoa học trưởng của Quân đoàn Thảm họa, dẫn dắt đội ngũ nghiên cứu của mình nỗ lực giải mã chúng. Sau một tháng nỗ lực gian khổ, nhóm nghiên cứu của bạn cuối cùng đã giải mã được cấu trúc năng lượng bên trong của viên ngọc Arcane loại 「$2$」 và loại 「$3$」.

Hai loại cấu trúc này có một số điểm tương đồng, bên trong chúng có $k$ lõi phản ứng. Mỗi lõi của viên ngọc loại 「$2$」 có thể coi là một lưới $2 \times n$, trong khi mỗi lõi của viên ngọc loại 「$3$」 có thể coi là một lưới $3 \times n$. (Lưu ý rằng $k$ và $n$ của các viên ngọc Arcane có thể khác nhau). Khi phản ứng thần lực diễn ra, mỗi lõi sẽ tự động được lấp đầy bởi các hạt thần lực.

Mô tả một cách hình thức, mỗi hạt thần lực có thể coi là một ô $1 \times 2$ đặt nằm ngang hoặc thẳng đứng. Việc lấp đầy lõi được định nghĩa là mỗi lưới phải được bao phủ hoàn toàn bởi các ô này sao cho không có ô nào chồng lấn. Nếu trong hai phương án lấp đầy lõi phản ứng, tồn tại một ô có vị trí hoặc cách đặt khác nhau, thì hai phương án đó được coi là khác nhau.

Ví dụ, có $5$ cách khác nhau để lấp đầy lưới $2 \times 4$ và $3$ cách khác nhau để lấp đầy lưới $3 \times 2$.

Nếu các cách lấp đầy của $k$ lõi trong viên ngọc Arcane đều khác nhau, chúng sẽ kết hợp tạo thành các thuật chú mạnh mẽ. Hắc Bào muốn biết có tổng cộng bao nhiêu loại thuật chú khác nhau cho một viên ngọc (đối với hai tổ hợp thuật chú, nếu với mỗi lõi $a$ trong tổ hợp thứ nhất, ta đều có thể tìm thấy một lõi $b$ trong tổ hợp thứ hai sao cho cách lấp đầy của $a$ và $b$ hoàn toàn giống nhau, thì hai tổ hợp thuật chú đó được coi là giống nhau).

Đối với viên ngọc Arcane loại 「$2$」 có chiều rộng $n$ và số lượng lõi phản ứng là $k$, gọi số thuật chú khác nhau là $F(n,k)$; đối với viên ngọc Arcane loại 「$3$」 có chiều rộng $n$ và số lượng lõi phản ứng là $k$, gọi số thuật chú khác nhau là $G(n,k)$. Ví dụ: $F(4,1) = 5, F(4,2) = 10, G(2,2) = 3$.

Trình độ công nghệ của Quân đoàn Thảm họa vẫn chưa thể đo đạc chính xác chiều dài $n$ của lõi phản ứng, chỉ có thể xác định phạm vi gần đúng $[l, r]$ của chiều dài lõi. Bạn cần tính toán số lượng thuật chú trung bình khi chiều dài lõi phản ứng nằm trong khoảng này, tức là:

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

Giả sử kết quả cuối cùng có dạng $\frac{A}{B}$, hãy xuất ra kết quả của $A \times B^{-1} \bmod 998244353$, trong đó $B^{-1}$ là nghịch đảo nhân của $B$ theo modulo $998244353$.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên dương $T$ và $m$, lần lượt là số lượng bộ dữ liệu và loại ngọc Arcane (chỉ có thể là $2$ hoặc $3$).

$T$ dòng tiếp theo, mỗi dòng chứa ba số nguyên dương $l, r, k$, biểu thị phạm vi chiều dài lõi và số lượng lõi.

Dữ liệu ra

Với mỗi bộ dữ liệu, nếu $m=2$ thì xuất ra $\mathrm{ans2}$, nếu $m=3$ thì xuất ra $\mathrm{ans3}$.

Ví dụ

Ví dụ 1

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

Kết quả 1

665496240
218802505
745517510
133015204
910014966

Ví dụ 2

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

Kết quả 2

3
900767573
52671648
600503426
678428567

Nhiệm vụ con

Với $100\%$ dữ liệu, thỏa mãn:

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