排列

题号：NC316183
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 给定整数 $n$ ，考虑一个长度为 $n$ 的排列 $p_1, p_2, \dots, p_n$ 。令 $D_t$ 为排列 $p$ 的第 $t$ 个前缀 $\{p_1, p_2, \dots, p_t\}$ 内的正序对数，即：

$\displaystyle D_t=\Big\lvert \Big\{(i,j) ~\Big\vert~ 1\leqslant i<j\leqslant t,\ p_i<p_j\Big\} \Big\rvert$

$\hspace{15pt}$ 其中， $\Big\lvert \Big\{(i,j) ~\Big\vert~ 条件\Big\} \Big\rvert$ 表示满足条件的 $(i,j)$ 对数。

$\hspace{15pt}$ 现在，共有 $q$ 次询问，每次询问求满足 $l_i\leqslant D_{t_i}\leqslant r_i$ 的“合法不同排列”的数目。由于答案可能很大，请将答案对 $998\,244\,353$ 取模后输出。

【名词解释】
$\hspace{15pt}$ 长度为 $n$ 的排列：由 $1,2,\dots,n$ 这 $n$ 个整数、按任意顺序组成的数组（每个整数均恰好出现一次）。例如， $\{2,3,1,5,4\}$ 是一个长度为 $5$ 的排列，而 $\{1,2,2\}$ 和 $\{1,3,4\}$ 都不是排列，因为前者存在重复元素，后者包含了超出范围的数。

输入描述:

第一行输入两个整数 ，表示排列  的长度、询问次数。
此后  行，第  行输入三个整数 ，表示第  次询问的排列  的前缀长度、所询问区间。

除此之外，保证单个测试文件中，将  去重后的和不超过 。

输出描述:

在一行上输出  个整数，表示每一次询问的满足条件的“合法不同排列”的数目对  取模后的结果。

示例1

输入

复制

输出

复制

120 60 45 119 40 29

示例2

输入

复制

输出

复制

1814400 3326400 3024000 1623370 1319957

示例3

输入

复制

1000000 3
400000 1 800000
51612 5623 100000
5125 52 7566

输出

复制

116453273 215807084 467831332

备注:

在几乎全部的情况下，PyPy 的运行速度优于 Python，我们建议您选择对应版本的 PyPy 进行提交、而不是 Python。