UOJ Logo Universal Online Judge

UOJ

#346. 【清华集训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$ 输出。

样例一

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

限制与约定

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

下载

样例数据下载