5367 - 省选：2024 day2 第二题：重塑时光（timeline）
Time Limit : 2 秒
Memory Limit : 1024 MB
本题时间限制1.5秒
Input
第一行三个整数 n, m, k，分别描述事件的个数，事件之间先后顺序的条数以及小 S进行的剪断操作次数。 接下来 m 行，每行两个整数 u, v，表示一条事件发生时间的先后顺序要求。
Output
输出一行一个整数，表示所求答案
Examples
Input
2 1 1 1 2
Output
666666672
Input
3 0 2
Output
1
Input
4 4 4 1 2 1 3 1 4 2 4
Output
937500007
Hint
【样例 2 解释】 没有任何事件发生时间之间的先后顺序要求，因此无论怎样拼接都是可行的方案，答案为 1。
