Trips

The fire brigade of a small town has $N$ members, and not all of them know each other. The members are numbered with integers from $1$ to $N$.

After a hard summer season of fighting fires, the brigade plans to go on two nature trips over the next two weekends.

The travel agency sent offers that are valid only if at least $A$ people go on the first trip and at least $B$ people go on the second trip. Also, to avoid awkward situations on the trips, every two people who take part in the same trip must know each other.

Firefighter Mirko has been given the job of assigning the members so that every member takes part in at least one trip and all the conditions above hold. A member may go on both trips.

Given the acquaintances between the members, write a program that computes the number of ways Mirko can make the assignment. Two ways are different if some member takes part in some trip in one way and not in the other.

The first line contains four integers $N$, $M$, $A$, and $B$: the number of members of the brigade, the number of acquaintances between members, and the minimum numbers of people who must take part in the first and the second trip ($1 \le N \le 500$, $0 \le M \le N(N-1)/2$, $1 \le A, B \le N$).

Each of the next $M$ lines contains two integers $U$ and $V$ ($1 \le U, V \le N$, $U \ne V$). Each line means that the members numbered $U$ and $V$ know each other. No acquaintance is given more than once.

Print the total number of ways to assign the members to the trips on the first and only line. Because this number can be very large, print only its remainder when divided by $10007$.