Sorcerers of the Round Table

The sorcerers of the round table are holding their privy council again. As always, they began to squabble before the agenda was even presented, and the seating order around the table proved controversial enough.

There are $n$ sorcerers, each identified by the height of their pointed hat. The hat heights are pairwise distinct integers from 1 to $n$, and a taller hat means a more senior sorcerer. For aesthetic reasons, the hat heights of two sorcerers seated next to each other must differ by at most $p$.

Some sorcerers dislike others. If sorcerer $a$ dislikes sorcerer $b$, then $b$ may not sit immediately to the right of $a$. The chairman, whose hat has height $n$, has already sat down at the table. In how many ways can the remaining sorcerers be arranged around the table?

The first line contains three integers $n$, $k$, and $p$ ($1 \le n \le 10^6$, $0 \le k \le 100000$, $0 \le p \le 3$), separated by single spaces. They are the number of sorcerers, the number of dislikes, and the maximum allowed difference in height between adjacent hats.

Each of the next $k$ lines contains two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le n$, $a_i \ne b_i$), separated by a single space. This means the sorcerer with hat height $a_i$ dislikes the sorcerer with hat height $b_i$. Each ordered pair appears at most once.

One set of tests worth 16% of the total score has $n \le 5$. Another, disjoint set worth 16% has $p \le 2$.

Print a single integer: the number of possible arrangements, modulo $10^9 + 7$.

The sorcerers can sit around the table in one of the six orders: 53124, 53142, 52143, 53412, 52314, 53214.