#2331. 「清华集训 2017」某位歌姬的故事

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: samzhang

题目描述

IA 是一名会唱歌的女孩子。

IOI2018 就要来了,IA 决定给参赛选手们写一首歌,以表达美好的祝愿。这首歌一共有 n 个音符,第 i 个音符的音高为 h_i 。IA 的音域是 A ,她只能唱出 1\sim A 中的正整数音高。因此 1\le h_i\le A

在写歌之前,IA 需要确定下这首歌的结构,于是她写下了 Q​ 条限制,其中第 i​ 条为:编号在 l_i​ r_i​ 之间的音符的最高音高为 m_i​ 。在确定了结构之后,她就可以开始写歌了。不过她还是想知道,一共有多少种可能的歌曲满足她的所有限制?她听说你还有 9 个月就要去 IOI 了,于是希望你帮她计算一下这个值。

输入格式

从标准输入读入数据。

输入的第一行包含一个整数 T(T\le 20) ,代表测试数据的组数。

每组数据的第一行包含三个正整数 n,Q,A 。接下来 Q 行,每行三个整数 l_i,r_i,m_i ,表示一条限制。保证 1\le l_i\le r_i\le n, 1\le m_i\le A

输出格式

输出到标准输出。

输出文件只有一行,表示可能的歌曲数目。这个数可能很大,请将答案模 998244353 输出。

样例

样例输入 1

1
3 2 3
1 2 3
2 3 2

样例输出 1

3

样例解释 1

以下是三种可能的歌曲: (3,1,2),(3,2,1),(3,2,2)

样例输入 2

2
4 2 4
1 2 3
2 3 4
7 3 74
3 6 56
2 5 56
3 7 70

样例输出 2

20
160326468

数据范围与提示

测试点编号 n Q A m_i 分数
1 \leq 7 \leq A 5
2 \leq 10 \leq 500 \leq 9\times 10^8 10
3 \leq 500 \leq 10 8
4 \leq 500 =2 12
5 \leq 9\times 10^8 18
6 \leq 500 \leq 9\times 10^8 \leq A 28
7 \leq 9\times 10^8 19