Island

Welcome to the island of Bitcairn! It has everything: settlements, roads, a beautiful lake, the Internet, and a monster living in the lake that is ready to destroy the whole island. A monster in the lake?

Byteasar, governor of Bitcairn, has ordered you to prepare an evacuation plan for tourists in case of a monster attack. He gave you the following information about the island:

• The island is a ring. Its outer boundary is the boundary of the sea, and its inner boundary is the boundary of the lake.
• The settlements are numbered consecutively from $1$ to $n$.
• Settlements $1$ to $a$ are on the boundary of the lake. They are numbered clockwise or counterclockwise along that boundary.
• Settlements $a+1$ to $a+b$ are on the coast (the boundary of the sea). They are numbered clockwise or counterclockwise along the coast.
• There are $m$ roads connecting settlements. A road cannot pass through the lake, the sea, or another settlement. Two roads may intersect only at a shared endpoint, so the road network is a planar graph. Each road is either directed or undirected.
• Every tourist in a settlement on the lake boundary can reach the coast through the road network, possibly using several roads.

To enable evacuation, choose a subset of coastal settlements where seaports will be built. The plan is safe if and only if every tourist in a settlement on the lake boundary can reach at least one settlement on the sea boundary where a seaport is built. Count the safe plans.

The first line 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$).

Each of the next $m$ lines describes one road in one of two formats:

• $u_i$ -{-} $v_i$: a bidirectional road between settlements $u_i$ and $v_i$
• $u_i$ -> $v_i$: a directed road from settlement $u_i$ to settlement $v_i$

Here $1 \le u_i, v_i \le n$ and $u_i \neq v_i$. No two roads connect the same pair of settlements. The settlements and roads form a planar graph. From every settlement on the lake boundary, at least one coastal settlement can be reached.

Print the number of safe plans modulo $10^9+7$.

In the first test, a seaport must be built at settlement $6$ so that tourist $3$ is safe. Tourists $1$ and $2$ can also reach settlement $6$, so they are safe too. Therefore, it does not matter whether seaports are built at settlements $4$ and $5$.

In the second test, seaports must be built at at least two of settlements $4$, $5$, and $6$, which is enough to keep all tourists safe. It does not matter whether a seaport is built at settlement $7$. Checking by hand, there are $8$ safe plans in total.