지재군단의 군사 흑포는 잠입한 첩자를 통해 신비한 지팡이에 대한 정보를 입수했고, 아르카나 보석에 담긴 고대의 신비한 힘에 큰 관심을 갖게 되었습니다. 그는 여러 개의 아르카나 보석을 탈취한 뒤, 지재군단의 수석 과학자인 당신에게 연구원들을 이끌고 그 비밀을 풀 것을 명령했습니다. 한 달간의 고된 노력 끝에 연구팀은 「$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$가 두 번째 주술에 존재한다면, 이 두 주술 조합은 동일한 것으로 간주합니다.)

너비가 $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}$은 $998244353$에 대한 $B$의 모듈러 역원입니다.

입력

첫 번째 줄에는 두 개의 양의 정수 $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}$