#SXLK2024E. 重塑时光

重塑时光

题目描述

小 T 正在研究某段时间中所发生的事件。经观测,有 nn 个编号为 1n1\sim n 的事件在这段时间内按顺序依次发生,第 ii 个发生的是事件 pip_i。这个描述事件发生顺序的排列 pp 可称为这段时间的时间线

突然,邪恶生物小 S 攻击了这条时间线,将这 nn 个事件的发生顺序 pp 变为了在所有长为 nn 的排列中等概率随机选取的一个排列。不仅如此,小 S 还用剪刀把时间线剪断,通过进行 kk 次操作,将排列 pp 分割成了 (k+1)(k + 1) 段。

具体而言,在小 S 进行第 ii 次操作时,排列 pp 和之前所有插入的剪断点构成了一个长度为 (n+i1)(n + i - 1) 的序列。该序列包括所有相邻元素之间和序列开头、末尾处共有 (n+i)(n + i) 个插入位置。小 S 将从这些插入位置中等概率随机选取一个位置,插入一个新的剪断点。最后,小 S 从最终被插入的 kk 个剪断点处把序列剪开,将排列 pp 分割成了 (k+1)(k + 1) 段序列。这 (k+1)(k + 1) 段序列中可能有空序列。

为了拯救这条即将毁灭的时间线,小 T 决定把这 (k+1)(k + 1) 段序列按某种顺序重新拼接成一个长度为 nn 的排列,形成一条新的时间线。不过,由于事件之间存在一定的逻辑关系,事件的发生时间之间也存在一些先后顺序要求。经研究,共存在 mm 条先后顺序要求 (u,v)(u, v),要求事件 uu 的发生时间必须在事件v 之前。也就是说,uu 在时间线中的出现位置必须在 vv 之前。

请你设计程序,计算有多大的概率,存在至少一种重新排列这 (k+1)(k + 1) 段序列,并将其重新拼接为一条新的时间线的方案,能够使所有的 mm 条事件发生时间之间的先后顺序要求都得到满足。

为了避免精度误差,请你输出答案对 109+710^9 +7 取模的结果。形式化地,可以证明答案可被表示为一最简分数 pq\frac{p}{q},请你输出一个 xx 满足 0x<109+70 \le x < 10^9+7qxp(mod109+7)qx \equiv p \pmod {10^9+7}。可以证明在题目条件下这样的 xx 总是存在。

输入格式

第一行三个整数 n,m,kn, m, k,分别描述事件的个数,事件之间先后顺序的条数以及小 S 进行的剪断操作次数。

接下来 mm 行,每行两个整数 u,vu, v,表示一条事件发生时间的先后顺序要求。

输出格式

输出一行一个整数,表示所求答案。

2 1 1
1 2
666666672

【样例 1 解释】

假如事件 11 的发生时间早于事件 22,那么无论怎样拼接都是可行方案,一定可以满足要求。否则,只有剪断时间线的位置位于事件 11 和事件 22 的发生时间之间,才能满足要求。答案为 $\frac{1}{2}+\frac{1}{2}\times \frac{1}{3}=\frac{2}{3}$。

image

3 0 2
1

【样例 2 解释】

没有任何事件发生时间之间的先后顺序要求,因此无论怎样拼接都是可行的方案,答案为 11

4 4 4
1 2
1 3
1 4
2 4
937500007

【样例 4】

见附件中的 timeline4.in/ans

【样例 5】

见附件中的 timeline5.in/ans

该组样例满足数据范围中的特殊性质 B。

【样例 6】

见附件中的 timeline6.in/ans

该组样例满足数据范围中的特殊性质 A。

【样例 7】

见附件中的 timeline7.in/ans

【子任务】

对于所有测试数据,

  • 1n151 \le n \le 15
  • 0mn(n1)20 \le m \le \frac{n(n-1)}{2}0kn0 \le k \le n
  • 1u<vn1 \le u < v \le n,保证不存在两对 (u,v)(u,v) 完全相同。
测试点 nn mm kk 特殊性质
11 3\le 3 =n1=n-1 =0=0 B
22 5\le 5 n(n1)2\le \frac{n(n-1)}{2} n\le n
3,43,4 14\le 14 =n1=n-1 B
55 =0=0 A
66 n\le n
77 =0=0
88 =n(n1)2=\frac{n(n-1)}{2}
9,109,10 9\le 9 15\le 15
1111 13\le 13 n(n1)2\le \frac{n(n-1)}{2} =0=0
1212 n\le n
131713 \sim 17 14\le 14
182018\sim 20 15\le 15

特殊性质 A:对于每个事件 xx,至多存在一条先后顺序 (u,v)(u, v) 使得 v=xv = x

特殊性质 B:对于所有先后顺序 (u,v)(u, v),均满足 u=1u = 1