원탁의 마법사들

원탁의 마법사들이 다시 비밀 평의회를 열게 되었다. 늘 그랬듯 안건이 나오기도 전에 말다툼이 시작되었고, 테이블에 앉는 순서만으로도 논란이 충분히 컸다.

마법사는 모두 $n$명이며, 각자 뾰족한 모자의 높이로 구별된다. 모자 높이는 1부터 $n$까지의 서로 다른 정수이고, 모자가 높을수록 서열이 높다. 보기 좋게 하기 위해, 옆자리에 앉은 두 마법사의 모자 높이 차이는 $p$ 이하여야 한다.

일부 마법사는 다른 마법사를 싫어한다. 마법사 $a$가 마법사 $b$를 싫어하면, $b$는 $a$의 바로 오른쪽에 앉을 수 없다. 모자 높이가 $n$인 의장은 이미 테이블에 앉아 있다. 나머지 마법사들을 원탁에 앉히는 방법은 몇 가지인가?

첫 줄에 정수 $n$, $k$, $p$가 공백으로 구분되어 주어진다 ($1 \le n \le 10^6$, $0 \le k \le 100000$, $0 \le p \le 3$). 각각 마법사의 수, 싫어하는 관계의 수, 인접한 모자 높이의 최대 차이이다.

이어지는 $k$개의 줄에는 정수 $a_i$, $b_i$ ($1 \le a_i, b_i \le n$, $a_i \ne b_i$)가 공백으로 구분되어 주어진다. 이는 모자 높이가 $a_i$인 마법사가 모자 높이가 $b_i$인 마법사를 싫어한다는 뜻이다. 같은 순서쌍은 한 번만 나온다.

전체 점수의 16%에 해당하는 테스트 묶음에서는 $n \le 5$이다. 전체 점수의 16%에 해당하는, 앞의 묶음과 겹치지 않는 다른 묶음에서는 $p \le 2$이다.

가능한 배치의 수를 $10^9 + 7$로 나눈 나머지를 정수 하나로 출력한다.

마법사들은 다음 여섯 가지 순서 중 하나로 원탁에 앉을 수 있다: 53124, 53142, 52143, 53412, 52314, 53214.