题目描述
IA 是一名会唱歌的女孩子。
IOI2018 就要来了,IA 决定给参赛选手们写一首歌,以表达美好的祝愿。这首歌一共有 n 个音符,第 i 个音符的音高为 hi。IA 的音域是 A,她只能唱出 1∼A 中的正整数音高。因此 1≤hi≤A。
在写歌之前,IA 需要确定下这首歌的结构,于是她写下了 Q 条限制,其中第 i 条为:编号在 li 到 ri 之间的音符的最高音高为 mi。在确定了结构之后,她就可以开始写歌了。不过她还是想知道,一共有多少种可能的歌曲满足她的所有限制?她听说你还有 9 个月就要去 IOI 了,于是希望你帮她计算一下这个值。
输入格式
从标准输入读入数据。
输入的第一行包含一个整数 T(T≤20),代表测试数据的组数。
每组数据的第一行包含三个正整数 n,Q,A。接下来 Q 行,每行三个整数 li,ri,mi,表示一条限制。保证 1≤li≤ri≤n,1≤mi≤A。
输出格式
输出到标准输出。
输出文件只有一行,表示可能的歌曲数目。这个数可能很大,请将答案模 998244353 输出。
数据范围与提示
测试点编号 |
n |
Q |
A |
mi |
分数 |
1 |
≤7 |
≤A |
5 |
2 |
≤10 |
≤500 |
≤9×108 |
10 |
3 |
≤500 |
≤10 |
8 |
4 |
≤500 |
=2 |
12 |
5 |
≤9×108 |
18 |
6 |
≤500 |
≤9×108 |
≤A |
28 |
7 |
≤9×108 |
19 |