题目描述

你按照以下方式构造一个长度为 $10^5$ 的排列 $P = (P_1, P_2, \ldots, P_{10^5})$。

数轴上有 $1, 2, \ldots, 10^5$ 这些点。点 $i$ 和点 $j$ 之间的距离是 $|i - j|$。此外，有一个初始为空的序列 $P$。从任意点开始，重复以下操作，直到 $P$ 的长度达到 $10^5$：

• 令 $x$ 为当前点对应的数字。如果 $x$ 不在 $P$ 中，则将 $x$ 添加到 $P$ 的末尾。接着，移动到距离当前点小于等于 $K$ 的任意一个点。

回答以下 $Q$ 个查询：

• 给定整数 $N, L, R$。令从 $P$ 中移除大于 $N$ 的元素后得到的序列为 $P' = (P'_1, P'_2, \ldots, P'_N)$。在所有可能的 $P'$ 的排列中，回答满足 $P'_1$ 大于等于 $L$ 且小于等于 $R$ 的排列数量，结果对 $998244353$ 取模。

输入格式

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

$query_i$ 表示第 $i$ 个查询。

每个查询的格式如下：

$$N \ L \ R$$

输入满足以下约束：

• 所有输入均为整数。
• $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$

输出格式

输出 $Q$ 行。在第 $i$ 行，输出第 $i$ 个查询的答案。

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

提示

在样例输入 1 中，对于第一个查询，有四种可能的序列作为 $P'$：

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

翻译由 DeepSeek V3.2 完成