Description

There are $n$ people (numbered $1 \sim n$) sitting in a circle around a round table. For any two people sitting in adjacent seats, the absolute difference of their numbers must not exceed $p$. Among them, some people dislike others. If $a$ dislikes $b$, then $b$ cannot sit in the seat immediately to the right of $a$. Now, assuming the seat of person $n$ has been fixed, how many valid seating arrangements are there for the remaining people?

Input Format

The first line contains three integers $n,k,p$ ($1\le n\le {10}^6$, $0\le k\le {10}^5$, $0\le p\le 3$).
The next $k$ lines each contain two integers $a_i, b_i$ ($1\le a_i, b_i \le n$, $a_i \neq b_i$), meaning $a_i$ dislikes $b_i$. The same pair $a_i,b_i$ will not be repeated.

Output Format

Output a single integer, which is the number of valid arrangements modulo ${10}^9+7$.

5 2 3
1 3
5 4

6

Hint

Original title: Czarnoksiężnicy okrągłego stołu.

Translated by ChatGPT 5