#2331. 「清华集训 2017」某位歌姬的故事
题目描述
IA 是一名会唱歌的女孩子。
IOI2018 就要来了，IA 决定给参赛选手们写一首歌，以表达美好的祝愿。这首歌一共有 个音符，第 个音符的音高为 。IA 的音域是 ，她只能唱出 中的正整数音高。因此 。
在写歌之前，IA 需要确定下这首歌的结构，于是她写下了 Q 条限制，其中第 i 条为：编号在 li 到 ri 之间的音符的最高音高为 mi。在确定了结构之后，她就可以开始写歌了。不过她还是想知道，一共有多少种可能的歌曲满足她的所有限制？她听说你还有 9 个月就要去 IOI 了，于是希望你帮她计算一下这个值。
输入格式
从标准输入读入数据。
输入的第一行包含一个整数 ，代表测试数据的组数。
每组数据的第一行包含三个正整数 。接下来 行，每行三个整数 ，表示一条限制。保证 。
输出格式
输出到标准输出。
输出文件只有一行，表示可能的歌曲数目。这个数可能很大，请将答案模 输出。
样例
输入
1
3 2 3
1 2 3
2 3 2输出
3样例1解释
以下是三种可能的歌曲：。
样例
输入
2
4 2 4
1 2 3
2 3 4
7 3 74
3 6 56
2 5 56
3 7 70输出
20
160326468数据范围与提示
| 测试点编号 | 分数 | ||||
|---|---|---|---|---|---|
| 1 | 5 | ||||
| 2 | 10 | ||||
| 3 | 8 | ||||
| 4 | 12 | ||||
| 5 | 18 | ||||
| 6 | 28 | ||||
| 7 | 19 |
题目来源：fps-loj-small-pics.zip；FPS 共享题包，题包内第 125 题。保留原作者与原赛事署名。