2331 「清华集训 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$ 输出。

| 测试点编号 | $ 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 |