你刚刚学习了算法 冒泡排序,能够以非降序对数组进行排序。让我们定义函数 $$$\text{sort}(a)$$$ ,如以下伪代码所示:
function sort(array a):
rounds := 0
n := length of a
while a is not non-decreasing:
rounds := rounds + 1
for i from 1 to n - 1:
if a[i] > a[i + 1]:
swap(a[i], a[i + 1])
return rounds
如图所示,$$$\text{sort}(a)$$$的返回值表示使用以下命令使数组$$$a$$$按非降序排序所需的轮数 冒泡排序.
给定一个整数 $$$n$$$,以及 $$$m$$$ 整数元组 $$$(k_i,l_i,r_i)$$$ ($$$1\le i\le m$$$)。计算长度为$$$n$$$的排列数$$$^{\text{*}}$$$ $$$p$$$,以$$$998\,244\,353$$$为模,满足以下限制:
- 对于每个 $$$1\le i\le n$$$,让 $$$b_i=\text{sort}([p_1,p_2,\ldots,p_{i}])$$$,然后
- 对于每个 $$$1\le j\le m$$$,令 $$$x$$$ 为索引 $$$y$$$ ($$$1\le y\le n$$$) 的数量,使得 $$$b_y\le k_j$$$ 成立,则 $$$l_j\le x\le r_j$$$ 成立。
$$$^{\text{*}}$$$长度$$$n$$$的排列是一个由从$$$1$$$到$$$n$$$以任意顺序的$$$n$$$个不同整数组成的数组。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现两次),$$$[1,3,4]$$$也不是排列($$$n=3$$$但数组中有$$$4$$$)。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2\leq n\leq 10^6$$$, $$$0\leq m\leq 1000$$$)。
接下来是 $$$m$$$ 行,第 $$$i$$$ 行包含三个整数 $$$k_i$$$、$$$l_i$$$ 和 $$$r_i$$$ ($$$0\le k_i\le n - 1$$$, $$$1\le l_i\le r_i\le n$$$) — 限制。
保证所有测试用例的$$$m^2$$$总和不超过$$$10^6$$$。
输出
对于每个测试用例,输出一个整数 - 可能的排列数,以 $$$998\,244\,353$$$ 为模。
示例
输入复制
64 30 1 11 3 32 4 43 20 3 31 2 34 31 2 22 3 40 1 25 31 1 43 5 54 5 510 51 2 32 3 43 4 54 5 65 6 71000000 0
输出复制
21880192600373341033
注意
在第一个测试用例中,只有排列 $$$[3,1,4,2]$$$ 和 $$$[4,1,3,2]$$$ 满足限制。以$$$[3,1,4,2]$$$为例。让我们计算数组$$$b$$$:
- $$$\text{排序}([3])=0$$$;
- $$$\text{排序}([3,1])=1$$$;
- $$$\text{排序}([3,1,4])=1$$$;
- $$$\text{排序}([3,1,4,2])=2$$$。
因此,$$$b=[0,1,1,2]$$$。很容易证明它满足所有限制。
在第二个测试用例中,只有排列 $$$[1,2,3]$$$ 满足限制。
在第三个测试用例中,以下 $$$8$$$ 排列满足限制:
- $$$[2,3,1,4]$$$;
- $$$[2,4,1,3]$$$;
- $$$[3,2,1,4]$$$;
- $$$[3,4,1,2]$$$;
- $$$[3,4,2,1]$$$;
- $$$[4,2,1,3]$$$;
- $$$[4,3,1,2]$$$;
- $$$[4,3,2,1]$$$.