如果一个长度为 $10^5$ 的排列 $p = (p_1, p_2, \dots, p_{10^5})$ 可以通过以下方式构造，则称其为“有趣的”（interesting）：

• 考虑坐标轴上的点 $1, 2, \dots, 10^5$。
• 选择其中一个点作为当前点。
• 存在一个初始为空的序列 $p$。
• 重复以下操作，直到 $p$ 的长度为 $10^5$：令 $x$ 为当前点对应的数值。如果 $x$ 不在 $p$ 中，将 $x$ 添加到 $p$ 的末尾。然后移动到与 $x$ 的距离小于或等于 $k$ 的点之一。

点 $i$ 和 $j$ 之间的距离为 $|i - j|$。

你的任务是回答以下形式的询问：给定三个整数 $n, \ell$ 和 $r$。我们可以选取任意一个有趣的排列 $p$，然后构造 $s = (s_1, s_2, \dots, s_n)$：即从 $p$ 中移除所有大于 $n$ 的元素后得到的排列。在所有可能的 $s$ 中，求满足 $\ell \le s_1 \le r$ 的排列数量。

由于满足条件的排列数量可能非常大，请输出其对 $998\,244\,353$ 取模的结果。

输入格式

第一行包含两个整数 $k$ 和 $q$：最大距离和询问次数（$1 \le k \le 10^5$；$2 \le q \le 2 \cdot 10^5$）。接下来 $q$ 行，每行包含一个询问：三个整数 $n, \ell$ 和 $r$（$1 \le n \le 10^5$；$1 \le \ell \le r \le n$）。

输出格式

输出 $q$ 行。第 $i$ 行输出第 $i$ 个询问的答案。

样例

样例输入 1

2 4
4 1 3
3 1 1
9 3 7
1 1 1

样例输出 1

16
2
27160
1

样例输入 2

256 2
3 1 2
65536 1024 32768

样例输出 2

4
517264494