CF2146F.Bubble Sort

You have just learned the algorithm bubble sort, which is able to sort an array in non-descending order. Let's define the function $\text{sort}(a)$ as in the following pseudocode:

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

As it is shown, the return value of $\text{sort}(a)$ represents the number of rounds needed to make array $a$ sorted in non-descending order by using bubble sort.

You are given an integer $n$, as well as $m$ integer tuples $(k_i,l_i,r_i)$ ($1\le i\le m$). Count the number of permutations$^{\text{∗}}$ $p$ of length $n$, modulo $998\,244\,353$, so that the following restrictions are satisfied:

• For each $1\le i\le n$, let $b_i=\text{sort}([p_1,p_2,\ldots,p_{i}])$, then
• For each $1\le j\le m$, let $x$ be the number of indices $y$ ($1\le y\le n$) such that $b_y\le k_j$, then $l_j\le x\le r_j$ holds.

$^{\text{∗}}$A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).

你刚刚学习了冒泡排序算法，该算法可以将一个数组按非降序排列。我们定义函数 $\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$ 变为非降序所需进行的轮数（round）。

给定一个整数 $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$ 表示满足 $b_y\le k_j$ 的下标 $y$（其中 $1\le y\le n$）的个数，则需满足 $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$）。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($2\leq n\leq 10^6$, $0\leq m\leq 1000$).

Then $m$ lines follow, the $i$-th line containing three integers $k_i$, $l_i$, and $r_i$ ($0\le k_i\le n - 1$, $1\le l_i\le r_i\le n$) — the restrictions.

It is guaranteed that the sum of $m^2$ over all test cases does not exceed $10^6$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each test case, output a single integer — the number of possible permutations, modulo $998\,244\,353$.

对于每个测试用例，输出一个整数——可能的排列数对 $998\,244\,353$ 取模的结果。

In the first test case, only permutations $[3,1,4,2]$ and $[4,1,3,2]$ satisfy the restrictions. Take $[3,1,4,2]$ as an example. Let's calculate the array $b$:

• $\text{sort}([3])=0$;
• $\text{sort}([3,1])=1$;
• $\text{sort}([3,1,4])=1$;
• $\text{sort}([3,1,4,2])=2$.

Thus, $b=[0,1,1,2]$. It is easy to show that it satisfies all the restrictions.

In the second test case, only permutation $[1,2,3]$ satisfies the restrictions.

In the third test case, the following $8$ permutations satisfy the restrictions:

• $[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]$.

在第一个测试用例中，仅有排列 $[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]$。