1359: #2331. 「清华集训 2017」某位歌姬的故事

Memory Limit:512 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

IA 是一名会唱歌的女孩子。

IOI2018 就要来了,IA 决定给参赛选手们写一首歌,以表达美好的祝愿。这首歌一共有 nnn 个音符,第 iii 个音符的音高为 hih_ihi。IA 的音域是 AAA,她只能唱出 1∼A1\sim A1A 中的正整数音高。因此 1≤hi≤A1\le h_i\le A1hiA

在写歌之前,IA 需要确定下这首歌的结构,于是她写下了 Q 条限制,其中第 i 条为:编号在 liri 之间的音符的最高音高为 mi。在确定了结构之后,她就可以开始写歌了。不过她还是想知道,一共有多少种可能的歌曲满足她的所有限制?她听说你还有 9 个月就要去 IOI 了,于是希望你帮她计算一下这个值。

输入格式

从标准输入读入数据。

输入的第一行包含一个整数 T(T≤20)T(T\le 20)T(T20),代表测试数据的组数。

每组数据的第一行包含三个正整数 n,Q,An,Q,An,Q,A。接下来 QQQ 行,每行三个整数 li,ri,mil_i,r_i,m_ili,ri,mi,表示一条限制。保证 1≤li≤ri≤n,1≤mi≤A1\le l_i\le r_i\le n, 1\le m_i\le A1lirin,1miA

输出格式

输出到标准输出。

输出文件只有一行,表示可能的歌曲数目。这个数可能很大,请将答案模 998244353998244353998244353 输出。

样例

输入

1
3 2 3
1 2 3
2 3 2

输出

3

样例1解释

以下是三种可能的歌曲:(3,1,2),(3,2,1),(3,2,2)(3,1,2),(3,2,1),(3,2,2)(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 n n Q Q Q A A A mi m_i mi 分数
1 ≤7 \leq 7 7 ≤7 \leq 7 7 ≤7 \leq 7 7 ≤A \leq A A 5
2 ≤10 \leq 10 10 ≤500 \leq 500 500 ≤9×108 \leq 9\times 10^8 9×108 ≤A \leq A A 10
3 ≤500 \leq 500 500 ≤10 \leq 10 10 ≤9×108 \leq 9\times 10^8 9×108 ≤A \leq A A 8
4 ≤500 \leq 500 500 ≤500 \leq 500 500 =2 =2 =2 =2 =2 =2 12
5 ≤9×108 \leq 9\times 10^8 9×108 ≤500 \leq 500 500 =2 =2 =2 =2 =2 =2 18
6 ≤500 \leq 500 500 ≤500 \leq 500 500 ≤9×108 \leq 9\times 10^8 9×108 ≤A \leq A A 28
7 ≤9×108 \leq 9\times 10^8 9×108 ≤500 \leq 500 500 ≤9×108 \leq 9\times 10^8 9×108 ≤A \leq A A 19