题目描述

$n$ 个人（编号为 $1 \sim n$）围着圆桌坐成一圈。座位相邻的两个人，其编号之差的绝对值不可以超过 $p$。他们之中有些人不喜欢别人。如果 $a$ 不喜欢 $b$，那么 $b$ 不能坐在 $a$ 右边的那一个位置上。现在，假设第 $n$ 个人的座位已经固定，要给剩下的人安排座位，共有几种合法方案？

输入格式

第一行包含三个整数 $n,k,p$（$1\le n\le {10}^6$，$0\le k\le {10}^5$，$0\le p\le 3$）。接下来 $k$ 行，每行含两个整数 $a_i, b_i$（$1\le a_i, b_i \le n$，$a_i \neq b_i$），表示 $a_i$ 不喜欢 $b_i$。同一组 $a_i,b_i$ 不会重复输入。

输出格式

输出一个整数，表示方案数模 ${10}^9+7$ 后的值。

5 2 3
1 3
5 4

6

提示

原题名称：Czarnoksiężnicy okrągłego stołu。