섬

비트케언 섬에 오신 것을 환영합니다! 이 섬에는 마을, 도로, 아름다운 호수, 인터넷, 섬 전체를 파괴하려고 호수에 사는 괴물까지 모두 있습니다. 잠깐, 호수에 괴물이라고요?

비타이자스 비트케언 총독이 방금 괴물이 공격할 경우에 대비해 관광객 대피 계획을 세우라고 지시했습니다. 총독이 섬에 대해 알려 준 정보는 다음과 같습니다.

• 섬에는 1부터 n까지 번호가 붙은 n개의 마을이 있습니다.
• 호숫가에는 a개의 마을이 있으며, 호숫가를 따라 시계 방향 또는 반시계 방향으로 1부터 a까지 번호가 붙어 있습니다.
• 바닷가에는 b개의 마을이 있으며, 바닷가를 따라 시계 방향 또는 반시계 방향으로 a + 1부터 a + b까지 번호가 붙어 있습니다.
• 마을들은 m개의 도로로 연결되어 있습니다. 각 도로는 두 마을을 잇고, 호수, 바다, 다른 마을을 지나지 않으며, 고가도로나 터널도 아닙니다. 또한 어느 두 도로도 서로 교차하지 않습니다(*). 각 도로는 일방통행 또는 양방향입니다.
• 모든 관광객은 호숫가 마을에 머뭅니다. 호숫가의 각 마을에서 여러 도로를 거치면 적어도 하나의 바닷가 마을에 도달할 수 있다고 가정해도 됩니다.

대피를 가능하게 하려면 항구를 건설하는 계획을 세워야 합니다. 계획은 어느 바닷가 마을에 항구를 지을지, 어느 항구를 포기할지를 정합니다. 호숫가에 사는 관광객이 모두 적어도 하나의 항구에 도달할 수 있어야만 계획이 관광객을 안전하게 지킵니다. 어떤 마을에 항구가 있는지가 두 계획에서 다르면, 두 계획은 서로 다른 계획입니다.

비타이자스는 섬을 안전하게 만드는 건설 계획이 몇 가지인지 알고 싶어 합니다. 결과가 클 수 있으니 10^9 + 7로 나눈 나머지만 구하면 됩니다. 서두르세요. 관광객의 안전이 당신에게 달려 있습니다!

(*) 달리 말하면, 마을과 도로로 이루어진 그래프는 평면 그래프입니다.

첫 줄에 정수 $n$, $m$, $a$, $b$가 주어집니다 ($2 \le n \le 500000$, $1 \le m \le 1000000$, $a, b \ge 1$, $a + b \le n$). 각각 마을 수, 도로 수, 호숫가 마을 수, 바닷가 마을 수입니다.

다음 $m$개의 줄은 도로를 나타내며, 아래 두 형식 중 하나입니다 ($1 \le u_i, v_i \le n$, $u_i \ne v_i$).

• u_i -- v_i: $u_i$와 $v_i$를 잇는 양방향 도로
• u_i -> v_i: $u_i$에서 $v_i$로 가는 일방통행 도로

같은 두 마을을 잇는 도로는 둘 이상 없습니다. 도로들은 서로 교차하지 않으며, 어떤 도로도 다른 마을, 호수, 바다를 지나지 않습니다. 또한 호숫가의 각 마을에서 적어도 하나의 바닷가 마을에 도달할 수 있다고 보장됩니다.

안전을 보장하는 항구 건설 방법의 수를 한 줄에 출력합니다. 답은 10^9 + 7로 나눈 나머지입니다.

첫 번째 예제에서 섬 당국은 3번 마을의 관광객이 섬을 떠날 수 있도록 6번 마을에 항구를 지어야 합니다. 1번과 2번 마을의 관광객도 이 항구에 갈 수 있으므로, 4번과 5번 마을에 항구를 지을지는 상관없습니다.

두 번째 예제에서는 4, 5, 6번 마을 중 적어도 두 곳에 항구를 지어야 합니다. 호숫가의 각 마을은 4, 5, 6번 중 두 곳에 도달할 수 있으며, 8번 마을에서 항구로 가는 길이 반드시 있을 필요는 없습니다. 7번 마을에 항구를 지을지는 상관없습니다. 안전을 보장하는 항구 집합은 8가지 방법으로 만들 수 있습니다.