CFCF2146F.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$ 取模。

在第一个测试点中，只有排列 $[3,1,4,2]$ 和 $[4,1,3,2]$ 满足条件。以下以 $[3,1,4,2]$ 为例，计算其 $b$ 数组：

• $\text{sort}([3])=0$；
• $\text{sort}([3,1])=1$；
• $\text{sort}([3,1,4])=1$；
• $\text{sort}([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]$。