Permutation Counting

题号：NC303735
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 这天小红给了小苯一个长度为 $n$ 的排列 $p$ ，但她把 $p$ 隐藏了起来，只告诉了小苯 $m$ 条有关 $p$ 的信息，具体的：

$\hspace{23pt}\bullet\,$ 第 $i\left(1 \leqq i \leqq m\right)$ 条信息包含 $3$ 个参数 $l_i, r_i, k_i$ ，表示 $p$ 在区间 $[l_i,r_i]$ 中的最大值等于 $k_i$ 。

$\hspace{30pt}$ 形式化地， $\max\left(p_{l_i},p_{l_i+1},\dots,p_{r_i}\right)=k_i$ 。

$\hspace{15pt}$ 你的任务则是帮助小苯确定，有多少种可能的排列 $p$ 都符合上述的所有信息。由于答案可能很大，请将答案对 $998\,244\,353$ 取模后输出。当然也有可能不存在这样的排列，此时输出 $0$ 。

【名词解释】
$\hspace{15pt}$ 长度为 $n$ 的排列：由 $1,2,\dots,n$ 这 $n$ 个整数、按任意顺序组成的数组（每个整数均恰好出现一次）。例如， $\{2,3,1,5,4\}$ 是一个长度为 $5$ 的排列，而 $\{1,2,2\}$ 和 $\{1,3,4\}$ 都不是排列，因为前者存在重复元素，后者包含了超出范围的数。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：

第一行输入两个正整数 ，表示排列  的长度、信息条数。
此后  行，第  行输入三个正整数 ，描述第  条信息。

除此之外，保证单个测试文件的  之和、 之和均不超过 。

输出描述:

对于每一组测试数据，新起一行输出一个整数，表示可能的排列个数对  取模后的答案。

示例1

输入

复制

输出

复制

说明

对于第一组测试数据，长度为  的排列中，满足在区间  中的最大值等于  的排列有：、 两个。

对于第四组测试数据，长度为  的排列，在区间  中的最大值一定是 ；而信息中说是  显然不可能，因此不存在这样的排列。