소풍

어느 작은 도시의 소방대에는 $N$명의 대원이 있고, 대원끼리 모두 서로 아는 사이는 아니다. 대원에게는 $1$부터 $N$까지 번호가 붙어 있다.

힘든 여름 화재 진압 시즌을 마친 소방대는 앞으로 두 주말 동안 자연으로 소풍을 두 번 가려고 한다.

여행사가 보낸 제안은 첫 번째 소풍에 $A$명 이상, 두 번째 소풍에 $B$명 이상이 참가해야만 유효하다. 또 소풍에서 어색한 상황이 생기지 않도록, 같은 소풍에 참가하는 두 사람은 반드시 서로 아는 사이여야 한다.

소방관 미르코는 모든 대원이 적어도 한 번의 소풍에 참가하고 위 조건을 모두 만족하도록 대원을 배정하는 일을 맡았다. 한 대원이 두 소풍에 모두 참가해도 된다.

대원 사이의 아는 관계가 주어질 때, 미르코가 배정을 정하는 방법의 수를 구하는 프로그램을 작성하시오. 어떤 대원이 어떤 소풍에 참가하는지 여부가 하나라도 다르면 서로 다른 방법으로 센다.

첫째 줄에 네 정수 $N$, $M$, $A$, $B$가 주어진다. 차례로 소방대 대원 수, 대원 사이의 아는 관계 수, 첫 번째 소풍과 두 번째 소풍에 참가해야 하는 최소 인원이다. ($1 \le N \le 500$, $0 \le M \le N(N-1)/2$, $1 \le A, B \le N$)

다음 $M$개의 줄에는 각각 두 정수 $U$와 $V$가 주어진다. ($1 \le U, V \le N$, $U \ne V$) 각 줄은 $U$번 대원과 $V$번 대원이 서로 아는 사이라는 뜻이다. 같은 관계는 두 번 이상 주어지지 않는다.

첫째 줄에 대원을 소풍에 배정하는 방법의 총 수를 출력한다. 이 수는 매우 클 수 있으므로 $10007$로 나눈 나머지를 출력한다.