Island

Welcome to Bitcairn Island! We have it all: settlements, roads, a beautiful lake, Internet, a monster living in the lake ready to destroy the whole island, perfect tropical weather... Wait, a monster in the lake?

Bytesius, governor of Bitcairn, has just asked you to prepare an evacuation plan for tourists in case the monster attacks. He gave you the following information about the island:

• The island has n settlements numbered from 1 to n.
• a settlements lie on the lake shore, numbered 1 to a along the shore, either clockwise or counterclockwise.
• b settlements lie on the sea shore, numbered a + 1 to a + b along the shore, either clockwise or counterclockwise.
• The settlements are connected by m roads. Each road connects two settlements, does not pass through the lake, the sea, or other settlements, and is not an overpass or tunnel. No two roads cross (*). Each road is one-way or two-way.
• All tourists live in lake-side settlements. You may assume that from each lake-side settlement, one can reach at least one sea-side settlement, possibly using several roads.

To make evacuation possible, you must design a port construction plan. The plan states in which sea-side settlements ports should be built and which ports should be dropped. The plan keeps tourists safe only if every tourist living in a lake-side settlement can reach at least one port. Two construction plans are different if a port exists in some settlement under one plan but not the other.

Bytesius wants to know how many construction plans keep the island safe. The answer may be large, so output it modulo $10^9 + 7$. Hurry, the safety of the tourists depends on you!

(*) In other words, the graph formed by settlements and roads is planar.

The first line contains four integers $n$, $m$, $a$, and $b$ ($2 \le n \le 500000$, $1 \le m \le 1000000$, $a, b \ge 1$, $a + b \le n$): the number of settlements, the number of roads, the number of lake-side settlements, and the number of sea-side settlements.

Each of the next $m$ lines describes a road in one of two forms ($1 \le u_i, v_i \le n$, $u_i \ne v_i$):

• u_i -- v_i: a two-way road between $u_i$ and $v_i$.
• u_i -> v_i: a one-way road from $u_i$ to $v_i$.

No pair of settlements is connected by more than one road. The roads do not cross, and no road passes through another settlement, the lake, or the sea. It is also guaranteed that from each lake-side settlement one can reach at least one sea-side settlement.

Print one integer: the number of ways to build ports in the sea-side settlements so that the island is safe, modulo $10^9 + 7$.

In the first example, the authorities must build a port in settlement 6 so that tourists from settlement 3 can leave the island. Tourists from settlements 1 and 2 can also reach this port, so it does not matter whether ports are built in settlements 4 and 5.

In the second example, ports must be built in at least two of settlements 4, 5, and 6. Each lake-side settlement can reach two of settlements 4, 5, and 6, and settlement 8 does not need a road to a port. Whether a port is built in settlement 7 does not matter. The safe port sets can be built in 8 ways.