Welcome to the island of Bitcairn! We have everything here – settlements, roads, a beautiful lake, the Internet, a monster living in the lake ready to destroy the entire island, and perfect tropical weather. . . Wait, a monster in the lake?

Bajtezjusz, the governor of Bitcairn, has just tasked you with preparing an evacuation plan for tourists from the island in case of a monster attack. He has provided you with the following information about the island:

• There are $n$ settlements on the island, numbered from $1$ to $n$.
• There are $a$ settlements on the shore of the lake, numbered from $1$ to $a$ along the lake shore, either clockwise or counter-clockwise.
• There are $b$ settlements on the seashore, numbered from $a + 1$ to $a + b$ along the seashore, either clockwise or counter-clockwise.
• The settlements are connected by $m$ roads. Each road connects two settlements, does not pass through the lake, the sea, or other settlements, and does not run on overpasses or through tunnels. Furthermore, no two roads intersect*. Each road is either one-way or two-way.
• All tourists live in the settlements by the lake. You can assume that from every settlement by the lake, it is possible to reach at least one coastal settlement, possibly using multiple roads.

To enable evacuation, you must design a port construction plan. The plan describes in which coastal settlements ports should be built to be ready to take tourists off the island, and in which of the ports they should be abandoned. The plan ensures safety for tourists only if every tourist living in a settlement by the lake is able to reach at least one port. Two construction plans are different if a port is built in a certain settlement in only one of these plans.

Bajtezjusz would like to know from you how many safety-ensuring port construction plans exist. Since the result can be large, it is sufficient to provide its remainder when divided by $10^9 + 7$. Hurry up – the safety of the tourists depends on you!

Input

The first line of input contains four integers $n, m, a$ and $b$ ($2 \le n \le 500\,000$, $1 \le m \le 1\,000\,000$, $a, b \ge 1$, $a + b \le n$), representing, respectively: the number of settlements on the island, the number of roads connecting them, and the number of settlements lying on the shore of the lake and the sea, respectively.

The next $m$ lines of input describe the roads on the island; each of them is of one of the following forms (where $1 \le u_i, v_i \le n$ and $u_i \neq v_i$):

• $u_i$ -- $v_i$ (denotes a two-way road connecting settlements $u_i$ and $v_i$),
• $u_i$ -> $v_i$ (denotes a one-way road leading from settlement $u_i$ to settlement $v_i$).

No pair of roads connects the same pair of settlements. You can assume that the settlements and roads are laid out in such a way that no two roads intersect and no road passes through other settlements, the lake, or the sea. Furthermore, from every settlement lying on the shore of the lake, one can reach at least one coastal settlement.

Output

The output should contain a single integer – the remainder when dividing by $10^9 + 7$ the number of ways we can build ports in the coastal settlements so that the island becomes safe.

* In other words, the graph defined by the settlements and roads is planar.

Examples

Input 1

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

Output 1

4

Input 2

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

Output 2

8

Note

Explanation of the examples: In the first example, the island authorities must build a port in settlement 6 so that tourists from settlement 3 can get off the island. Tourists from settlements 1 and 2 can also reach this port, so it is irrelevant whether we build ports in the remaining settlements (numbered 4 and 5).

In the second example, ports must be built in at least two out of the three settlements 4, 5, and 6 (from every settlement on the lake shore one can reach two out of the settlements 4, 5, and 6, and from settlement 8 there does not have to be a road to a port). However, it does not matter whether a port in settlement 7 is built. It is easy to conclude that the set of ports guaranteeing safety can be built in 8 ways.

Subtasks

In some test groups, the following additional condition holds: from a certain settlement lying on the lake shore, one can reach every coastal settlement.

Furthermore, in some groups (possibly partially disjoint from the above), an additional condition $a, b \le 3000$ holds.