某位歌姬的故事
题目描述
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
输入样例 #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
说明
**样例1解释**
以下是三种可能的歌曲:$(3,1,2),(3,2,1),(3,2,2)$。
![0](https://cdn.luogu.com.cn/upload/pic/14340.png)