F. 气泡排序

每次测试时间限制：$2$ 秒
每次测试内存限制：$512$ 兆字节

你刚刚学会了泡泡排序算法，它可以按非降序排序数组。让我们定义函数 $\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$ 的数量（模 $998244353$），使其满足以下限制：

• 对于每个 $1 \le i \le n$，设 $b_i = \text{sort}([p_1, p_2, \dots, 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$ 成立。

排列的定义：
长度为 $n$ 的排列是由 $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$ 行，第 $i$ 行包含三个整数 $k_i, l_i, r_i$（$0 \le k_i \le n-1$，$1 \le l_i \le r_i \le n$）—— 限制条件。

保证所有测试用例的 $m$ 之和不超过 $10^6$。

---

输出

对于每个测试用例，输出一个整数 —— 满足条件的排列数量，模 $998244353$。

---

示例

输入

6
4 3
0 1 1
1 3 3
2 4 4
3 2
0 3 3
1 2 3
4 3
1 2 2
2 3 4
0 1 2
5 3
1 1 4
3 5 5
4 5 5
10 5
1 2 3
2 3 4
3 4 5
4 5 6
5 6 7
1000000 0

输出

2
1
8
80
192600
373341033

---

注释

第一个测试案例：
只有排列 $[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]$