A16629 | Bubble Sort

你刚刚学习了冒泡排序算法，它可以将一个数组按非降序排序。我们定义函数 $\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$ 的排列 $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$。

注：排列是长度为 $n$ 的数组，包含 $1$ 到 $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 \le n \le 10^6$，$0 \le m \le 1000$）。

随后 $m$ 行，每行三个整数 $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$ 取模。