#PQJ489x4616. QOJ 489_4616

    ID: 3009 传统题 1000ms 512MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:CTT 2017动态规划前缀和

QOJ 489_4616

标题: 某位歌姬的故事 - Problem - QOJ.ac

#4616. 某位歌姬的故事

Statistics

The problem was used in the following contests:

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 输出。

样例一

input

1
3 2 3
1 2 3
2 3 2

output

3

explanation

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

样例二

input

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

output

20
160326468

限制与约定

测试点编号nQAmi分数1≤7≤7≤7≤A52≤10≤500≤9×108≤A103≤500≤10≤9×108≤A84≤500≤500=2=2125≤9×108≤500=2=2186≤500≤500≤9×108≤A287≤9×108≤500≤9×108≤A19