[PA2019]Wyspa

内存限制：512 MiB 时间限制：60 Sec

比特岛位于海上，在比特岛的中心有一个内陆湖。

在比特岛一共有n个点，编号为1到n，其中1到a的点按照顺时针或者逆时针表示内陆湖边上的点，a+1到a+b的点按照顺时针或者逆时针表示比特岛海岸线上的点，a+b+1到n的点表示既不在湖边也不在海边的点。

这些点之间连着m条单向或双向道路。每条道路不会经过湖、海或者任意一个点；任意两点间只会连着最多一条道路；这些道路中不存在“天桥”或者“地下隧道”，任意两条道路只可能在端点处相交。换言之，这是一张平面图。并且从任意一个湖边的点出发，都能沿着这些道路直接或间接地到达至少一个海边的点。

现在要在b个海边点中选择若干个点作为港口，问有多少种选点的方案使得任意一个湖边的点都能到达至少一个港口？

第一行四个正整数n,m,a,b(2<=n<=500000,1<=m<=1000000,1<=a,b<=n,2<=a+b<=n)。

接下来m行描述m条道路，每行要么是“u -- v”要么是“u -> v”(1<=u,v<=n,u!=v)：

如果是“u -- v”，表示这是一条连接u和v的双向道路。

如果是“u -> v”，表示这是一条从u出发到达v的单向道路。

输出一行一个整数，即满足条件的方案数模10^9+7。


			6 8 3 3

2 -> 1

2 -> 3

1 -> 3

3 -- 6

1 -> 4

2 -> 5

4 -> 6

4 -- 5

6号点必选，4和5可选可不选，因此有4种方案。

#5555. [PA2019]Wyspa