【清华集训2017】某位歌姬的故事
题目描述
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
3 2 3
1 2 3
2 3 2
3
以下是三种可能的歌曲：$(3,1,2),(3,2,1),(3,2,2)$。
2
4 2 4
1 2 3
2 3 4
7 3 74
3 6 56
2 5 56
3 7 70
20
160326468
限制与约定
| 测试点编号 | $n$ | $Q$ | $A$ | $m_i$ | 分数 |
|---|---|---|---|---|---|
| 1 | $\leq 7$ | $\leq 7$ | $\leq 7$ | $\leq A$ | 5 |
| 2 | $\leq 10$ | $\leq 500$ | $\leq 9\times 10^8$ | $\leq A$ | 10 |
| 3 | $\leq 500$ | $\leq 10$ | $\leq 9\times 10^8$ | $\leq A$ | 8 |
| 4 | $\leq 500$ | $\leq 500$ | $=2$ | $=2$ | 12 |
| 5 | $\leq 9\times 10^8$ | $\leq 500$ | $=2$ | $=2$ | 18 |
| 6 | $\leq 500$ | $\leq 500$ | $\leq 9\times 10^8$ | $\leq A$ | 28 |
| 7 | $\leq 9\times 10^8$ | $\leq 500$ | $\leq 9\times 10^8$ | $\leq A$ | 19 |
时间限制：$1\texttt{s}$
空间限制：$512\texttt{MB}$