#P17980. Efficient Express
Efficient Express
Efficient Express
题目描述
一条线路有按顺序编号为 的车站,第 个车站的等级为 ,等级在 到 之间。
共有 种列车服务。第 种服务由三个参数 决定,停靠的车站恰好是:
- 且 的车站;
- 且 的车站。
两个不同的车站可以直接到达,当且仅当至少有一种列车服务同时停靠这两个车站。
已知所有 。求有多少个有序数组 ,其中 ,能使任意两个等级相同的不同车站均可以直接到达。答案对 取模。
输入格式
第一行三个整数 。
第二行 个整数 。
接下来 行,第 行两个整数 。
输出格式
输出一个整数,表示方案数模 的结果。
数据范围
,,。
,。不保证每个等级都出现在车站中,列车的已知参数允许相同。
样例 1
4 3 4
2 3 3 2
1 2
2 2
2 3
48
样例 2
7 3 5
2 4 3 2 4 2 3
2 2
4 3
5 2
80
样例 3
4 2 10
3 7 2 5
1 4
3 3
100
样例 3 中没有等级相同的不同车站,因此全部 种选择均合法。