岛屿 - 問題

欢迎来到 Bitcairn 岛！这里应有尽有——定居点、道路、美丽的湖泊、互联网，还有一个住在湖里、随时准备摧毁整个岛屿的怪物！等等，等等——湖里有怪物？！

Bitcairn 岛的总督 Byteasar 刚刚下令让你准备一份游客撤离计划，以应对怪物的袭击。他告诉了你关于该岛的以下信息：

该岛可以想象成一个环，其外边界是海的边界，内边界是湖的边界。
共有 $n$ 个定居点，编号为从 $1$ 到 $n$ 的连续整数。
编号为 $1$ 到 $a$ 的定居点位于湖的边界上。此外，它们沿着该边界按顺时针或逆时针方向编号。
编号为 $a + 1$ 到 $a + b$ 的定居点位于海岸（海的边界）上。此外，它们沿着海岸按顺时针或逆时针方向编号。
有 $m$ 条连接定居点的道路。每条道路都不能穿过湖泊、海洋或其他定居点。此外，两条道路只能在其公共端点处相交（如果它们有公共端点的话）。换句话说，道路网络构成了一个平面图。此外，每条道路可以是单向的，也可以是双向的。
所有游客都居住在位于湖边界上的定居点中。可以假设从这些定居点中的每一个出发，都可以通过道路网络（可能使用多条道路）到达海岸。

为了实现撤离，你需要设计一个建造海港的计划。该计划应包含一个沿海定居点的子集，将在这些定居点建造海港。当且仅当居住在湖边界上每个定居点的游客都能到达至少一个建造了海港的海岸定居点时，该计划才能确保所有游客的安全。

Byteasar 想知道，有多少种确保安全的计划？由于结果可能非常大，请输出其对 $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 号定居点中的至少两个建造海港，这足以确保所有游客的安全。是否在 7 号定居点建造海港并不重要。经核实，总共有 8 种确保安全的计划。

QOJ.ac