거리 순열

수직선 위에 점 $1, 2, \dots, 10^5$가 있습니다. 두 점 $i$, $j$ 사이의 거리는 $|i-j|$입니다.

길이가 $10^5$인 수열 $P = (P\_1, P\_2, \dots , P\_{10^5})$을 다음과 같이 만듭니다. 처음에 $P$는 비어 있습니다. 어느 점에서든 시작하여 $P$의 길이가 $10^5$가 될 때까지 다음 연산을 반복합니다.

• 현재 점에 대응하는 수를 $x$라 합니다. $x$가 $P$에 없으면 $x$를 $P$의 끝에 추가합니다. 그다음 거리가 $K$ 이하인 점 중 하나로 이동합니다.

$Q$개의 질의에 답합니다. 각 질의에서는 정수 $N$, $L$, $R$이 주어집니다. $P$에서 $N$보다 큰 원소를 모두 제거한 수열을 $P' = (P'\_1, P'\_2, \dots , P'\_N)$이라 합니다. $P'$가 될 수 있는 순열 중에서 $P'\_1$이 $L$ 이상 $R$ 이하인 순열의 개수를 $998244353$으로 나눈 나머지를 구하세요.

첫 줄에 $K$와 $Q$가 주어집니다. 이어서 $Q$개의 줄에 각 질의가 $N$ $L$ $R$ 형식으로 주어집니다.

각 질의의 답을 한 줄에 하나씩 출력합니다.

• 모든 입력은 정수입니다.
• $1 \le Q \le 2 \times 10^5$
• $1 \le K \le 10^5$
• $1 \le N \le 10^5$
• $1 \le L \le R \le N$

예제 입력 1의 첫 번째 질의에서 $P'$가 될 수 있는 수열은 네 가지입니다.

• $(1, 2, 3, 4)$
• $(1, 2, 4, 3)$
• $(1, 3, 2, 4)$
• $(1, 3, 4, 2)$