#8179. 「省选联考 2024」 重塑时光 NOI/NOI+/CTSC

小 T 正在研究某段时间中所发生的事件。经观测，有 个编号为 的事件在这段时间内按顺序依次发生，第 个发生的是事件 。这个描述事件发生顺序的排列 可称为这段时间的时间线。

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

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

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

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

为了避免精度误差，请你输出答案对 取模的结果。形式化地，可以证明答案可被表示为一最简分数 ，请你输出一个 满足 且 。可以证明在题目条件下这样的 总是存在。

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

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

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

样例输入 1

2 1 1
1 2

样例输出 1

666666672

样例输入 2

3 0 2

样例输出 2

1

样例输入 3

4 4 4
1 2
1 3
1 4
2 4

样例输出 3

937500007

【样例 1 解释】

假如事件 的发生时间早于事件 ，那么无论怎样拼接都是可行方案，一定可以满足要求。否则，只有剪断时间线的位置位于事件 和事件 的发生时间之间，才能满足要求。答案为 。

【样例 2 解释】

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

【样例 4】

见附件中的 timeline4.in/ans。

【样例 5】

见附件中的 timeline5.in/ans。

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

【样例 6】

见附件中的 timeline6.in/ans。

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

【样例 7】

见附件中的 timeline7.in/ans。

【子任务】

对于所有测试数据，

• ，
• ，，
• ，保证不存在两对 完全相同。

特殊性质 A：对于每个事件 ，至多存在一条先后顺序 使得 。

特殊性质 B：对于所有先后顺序 ，均满足 。