P15714 [JAG 2023 Summer Camp #2] Distance Permutation

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.

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