题目描述

You construct a permutation $P = (P_1, P_2, \ldots, P_{10^5})$ of length $10^5$ in the following way.

The number line has points $1, 2, \ldots, 10^5$. The distance between points $i$ and $j$ is $|i - j|$. Also, there is a sequence $P$ that is initially empty. Repeat the following operations from any point until the length of $P$ is $10^5$.

• Let $x$ be the number corresponding to the current point. If $x$ is not in $P$, add $x$ to the end of $P$. Next, move to one of the points whose distance is less than or equal to $K$.

Answer the following $Q$ queries.

• You are given integers $N, L, R$. Let the sequence created by removing elements larger than $N$ from $P$ be $P' = (P'_1, P'_2, \ldots, P'_N)$. Among the possible permutations of $P'$, answer the number of permutations in which $P'_1$ is greater than or equal to $L$ and less than or equal to $R$ with mod $998244353$.

输入格式

$$\begin{aligned} &K \ Q \\ &query_1 \\ &\vdots \\ &query_Q \end{aligned} $$

$query_i$ represents the $i$-th query.

Each query is given in the following format.

$$N \ L \ R$$

The input satisfies the following constraints.

• All inputs consist of integers.
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq K \leq 10^5$
• $1 \leq N \leq 10^5$
• $1 \leq L \leq R \leq N$

输出格式

Output $Q$ lines. On the $i$-th line, output the answer of the $i$-th query.

2 4
4 1 1
3 1 3
10 2 7
1 1 1

4
6
140172
1

314 6
60522 7560 25373
79445 26896 78962
33447 12441 21469
47202 17227 32455
63982 13450 41311
2156 1226 2148

925500464
455690352
567782656
893053639
942918900
458845228

提示

In Sample Input 1, There are four possible sequences as $P'$ in the first query.

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