시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
7 초 | 512 MB | 9 | 2 | 2 | 100.000% |
Welcome to island Bitcairn! We have everything here -- settlements, roads, beautiful lake, the Internet and a monster living in the lake which is ready to destroy the whole island! Wait, wait, wait -- a monster in the lake?!
Byteasar, governor of Bitcairn, has just ordered you to prepare an evacuation plan for tourists in a case of monster's attack. He told you following information about the island:
In order to enable evacuation, you need to design a plan of building seaports. Such plan should contain subset of coastal settlements where seaports will be built and it ensures safety for all tourists if and only if each tourist living in settlement on the boundary of the lake can reach at least settlements on the boundary of the sea where seaports will be built.
Byteasar would like to know, what is the number of plans ensuring safety? Since the result can be huge, it is sufficient to print it modulo $10^9 +7$. You need to hurry up -- safety of tourists depends on you!
The first line of input contains four intergers $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$) denoting number of settlements, number of roads, number of settlements on the boundary of the lake and number of settlements on the boundary of the sea, respectively.
Following $m$ lines describe roads. Each of them contains a description of one road in the following format:
-{
-} $v_i$ (describing bidirectional road connecting settlements $u_i$ and $v_i$)->
$v_i$ (describing unidirectional road going from settlement $u_i$ to settlement $v_i$)where $1 \le u_i, v_i \le n$ and $u_i \neq v_i$.
No two roads connect the same pair of settlements. You can assume that these settlements and roads form a planar graph. Moreover for every settlement on the boundary of the lake at least one settlement on the coast can be reached.
You need to output one integer -- number of plans ensuring safety, modulo $10^9+7$.
6 8 3 3 2 -> 1 2 -> 3 1 -> 3 3 -- 6 1 -> 4 2 -> 5 4 -> 6 4 -- 5
4
8 7 3 4 1 -> 4 1 -> 5 2 -> 4 2 -> 8 3 -> 6 3 -> 5 8 -> 6
8
In the first test we need to build a seaport in a settlement number $6$ in order to ensure safety for tourists living in settlement number $3$. However, tourists from settlements number $1$ and $2$ are able to reach it as well, so they safety will be ensured as well in that case, so it doesn't matter whether we build seaports in settlements number $4$ and $5$.
In the second sample test we need to build seaports in at least two out of settlements in numbers $4$, $5$ and $6$ and that is sufficient to ensure safety of all tourists. It doesn't matter whether we build seaport in settlement number $7$. It can be readily checked that in total there are $8$ plans ensuring safety.