섬

비트케언 섬에 오신 것을 환영합니다. 이 섬에는 정착지, 도로, 아름다운 호수, 인터넷이 모두 있습니다. 호수에는 섬 전체를 파괴할 준비가 된 괴물이 살고 있습니다. 호수에 괴물이라고요?

비트케언의 총독 바이트아사르가 괴물 공격에 대비해 관광객을 위한 대피 계획을 세우라고 지시했습니다. 총독이 알려준 섬 정보는 다음과 같습니다.

• 섬은 고리 모양입니다. 바깥 경계는 바다의 경계이고, 안쪽 경계는 호수의 경계입니다.
• 정착지는 1번부터 $n$번까지 연속된 번호로 구분됩니다.
• 1번부터 $a$번 정착지는 호수의 경계 위에 있습니다. 이 정착지들은 경계를 따라 시계 방향 또는 반시계 방향으로 번호가 매겨져 있습니다.
• $a+1$번부터 $a+b$번 정착지는 해안(바다의 경계) 위에 있습니다. 이 정착지들은 해안을 따라 시계 방향 또는 반시계 방향으로 번호가 매겨져 있습니다.
• 정착지를 잇는 도로가 $m$개 있습니다. 도로는 호수, 바다, 다른 정착지를 지나갈 수 없습니다. 두 도로는 공통 끝점에서만 만날 수 있습니다. 즉 도로망은 평면 그래프입니다. 각 도로는 방향이 있거나 없습니다.
• 호수 경계의 정착지에 사는 관광객은 도로망을 따라 여러 도로를 거쳐서라도 해안에 도달할 수 있습니다.

대피를 가능하게 하려면 항구를 지을 해안 정착지의 부분집합을 정해야 합니다. 호수 경계에 사는 모든 관광객이 항구가 지어진 해안 정착지 중 적어도 한 곳에 도달할 수 있을 때에만 그 계획이 안전을 보장합니다. 안전을 보장하는 계획의 수를 구하세요.

첫 줄에 네 정수 $n$, $m$, $a$, $b$가 주어집니다($2 \le n \le 500\,000$, $1 \le m \le 1\,000\,000$, $a, b \ge 1$, $a + b \le n$).

이어지는 $m$개의 줄은 각각 다음 두 형식 중 하나로 도로를 나타냅니다.

• $u_i$ -{-} $v_i$: 정착지 $u_i$와 $v_i$를 잇는 양방향 도로
• $u_i$ -> $v_i$: 정착지 $u_i$에서 $v_i$로 가는 단방향 도로

여기서 $1 \le u_i, v_i \le n$이고 $u_i \neq v_i$입니다. 같은 두 정착지를 잇는 도로는 없습니다. 정착지와 도로는 평면 그래프를 이룹니다. 호수 경계의 모든 정착지에서 해안 정착지 하나 이상에 도달할 수 있습니다.

안전을 보장하는 계획의 수를 $10^9+7$로 나눈 나머지로 출력하세요.

첫 번째 테스트에서는 관광객 3번이 안전하려면 6번 정착지에 항구를 지어야 합니다. 1번과 2번 관광객도 6번 정착지에 도달할 수 있으므로 이들의 안전도 보장됩니다. 따라서 4번과 5번 정착지에 항구를 지을지는 상관이 없습니다.

두 번째 테스트에서는 4번, 5번, 6번 정착지 중 적어도 두 곳에 항구를 지어야 모든 관광객의 안전이 보장됩니다. 7번 정착지에 항구를 지을지는 상관이 없습니다. 직접 세어 보면 안전을 보장하는 계획은 모두 8가지입니다.