岛屿 [A] - Problem

欢迎来到 Bitcairn 岛！这里应有尽有——定居点、道路、美丽的湖泊、互联网、生活在湖中随时准备摧毁整个岛屿的怪物，以及完美的度假天气……等等，湖里有怪物？

Bitcairn 岛的总督 Bajtezjusz 刚刚委托你制定一份在怪物袭击时疏散岛上游客的计划。他向你提供了以下关于该岛的信息：

岛上有 $n$ 个定居点，编号为 $1$ 到 $n$。
湖岸边有 $a$ 个定居点，编号为 $1$ 到 $a$，沿湖岸按顺时针或逆时针方向排列。
海边有 $b$ 个定居点，编号为 $a + 1$ 到 $a + b$，沿海岸线按顺时针或逆时针方向排列。
定居点之间由 $m$ 条道路连接。每条道路连接两个定居点，不穿过湖泊、海洋或其他定居点，也不通过高架桥或隧道。此外，没有任何两条道路相交。每条道路可以是单向或双向的。
所有游客都居住在湖边的定居点。可以假设从湖边的每个定居点出发，至少可以到达一个海边的定居点（可能需要经过多条道路）。

为了实现疏散，你必须设计一个港口建设方案。该方案描述了在哪些海边定居点应该建造港口以准备接走游客，以及在哪些定居点不建造港口。只有当居住在湖边定居点的每位游客都能到达至少一个港口时，该方案才能确保游客的安全。如果两个方案中某个定居点是否建造港口的情况不同，则这两个方案被视为不同。

Bajtezjusz 想知道有多少种能确保安全的港口建设方案。由于结果可能很大，你只需要输出其对 $10^9 + 7$ 取模后的结果。抓紧时间——游客的安全取决于你！

输入的第一行包含四个整数 $n, m, a$ 和 $b$ ($2 \le n \le 500\,000, 1 \le m \le 1\,000\,000, a, b \ge 1, a + b \le n$)，分别表示岛上的定居点数量、连接它们的道路数量，以及分别位于湖岸和海边的定居点数量。

接下来的 $m$ 行描述了岛上的道路；每行采用以下格式之一（其中 $1 \le u_i, v_i \le n$ 且 $u_i \neq v_i$）：

没有两条道路连接同一对定居点。你可以假设定居点和道路的布局方式使得没有任何两条道路相交，且没有任何道路穿过其他定居点、湖泊或海洋。此外，从湖岸边的每个定居点出发，至少可以到达一个海边的定居点。

输出应包含一个整数——在海边定居点建造港口以确保岛屿安全的方法总数，对 $10^9 + 7$ 取模。

6 8 3 3
2 -> 1
2 -> 3
1 -> 3
3 -- 6
1 -> 4
2 -> 5
4 -> 6
4 -- 5

8 7 3 4
1 -> 4
1 -> 5
2 -> 4
2 -> 8
3 -> 6
3 -> 5
8 -> 6

在第一个样例中，岛屿当局必须在定居点 6 建造一个港口，以便来自定居点 3 的游客能够离开岛屿。来自定居点 1 和 2 的游客也可以到达这个港口，因此在其余定居点（编号 4 和 5）是否建造港口并不重要。

在第二个样例中，必须在定居点 4、5 和 6 中的至少两个建造港口（从湖岸边的每个定居点都可以到达 4、5 和 6 中的两个，而从定居点 8 不一定需要有通往港口的道路）。然而，在定居点 7 是否建造港口并不重要。不难推断，保证安全的港口集合共有 8 种建造方式。

在某些测试组中，额外满足以下条件：从某个湖岸边的定居点出发，可以到达每一个海边的定居点。

此外，在某些测试组中（可能与上述条件部分重叠），额外满足 $a, b \le 3000$。

QOJ.ac