样例文件

题目描述

小明要构造一个数列，要求满足以下条件：

（1）包含 n 个元素；

（2）每个元素为不超过 m 的正整数。

同时，还有 k 条限制，每条限制形如 a, b, c, 表示构造数列的第 a 个至第 b 个元素之间的元素最大值恰好为 c。

问：小明可能构造出多少个数列？输出结果 mod $998244353$。

多组数据。

输入格式

第一行：一个整数 $T$，表示数据组数。

对于每组数据：

• 第一行：三个整数 $n,k,m$；
• 接下来 $k$ 行，每行三个整数 $a, b, c$​​。

输出格式

共 $T$ 行，每组数据的答案占一行。

样例输入

1
3 2 5
1 2 2
2 3 5

样例输出

3

样例解释

可能构造出的数列有：

• 1, 2, 5
• 2, 1, 5
• 2, 2, 5

数据范围

$T ≤ 20, 1 ≤ a ≤ b ≤ n, 1 ≤ c ≤ m$。