圆桌会议的时刻又到了。和往常一样，巫师们在议程公布之前就开始了争吵：圆桌周围的座位顺序引发了巨大的争议。共有 $n$ 位巫师参加会议，每位巫师都由其尖顶帽的高度唯一标识；帽子的高度是 $1$ 到 $n$ 之间互不相同的整数（帽子越高，巫师的资历越深）。为了美观，相邻两位巫师的帽子高度之差必须不超过 $p$。

请注意，有些巫师并不喜欢其他人——如果巫师 $a$ 不喜欢巫师 $b$，那么巫师 $b$ 不能坐在巫师 $a$ 的正右侧。我们假设主席（戴着高度为 $n$ 的帽子）已经坐在了桌旁。请问剩下的巫师有多少种排列方式？

输入格式

标准输入的第一行包含三个整数 $n, k, p$（$1 \le n \le 1\,000\,000$，$0 \le k \le 100\,000$，$0 \le p \le 3$），分别表示巫师的人数、他们之间的厌恶关系数量以及相邻帽子高度允许的最大差值。

接下来的 $k$ 行包含有序对：第 $i$ 行包含两个整数 $a_i$ 和 $b_i$（$1 \le a_i, b_i \le n, a_i \neq b_i$），表示戴着高度为 $a_i$ 的帽子的巫师不喜欢戴着高度为 $b_i$ 的帽子的巫师。每对有序对在输入中最多出现一次。

有一组测试数据占总分的 $16\%$，其中满足 $n \le 5$。另有一组不相交的测试数据占总分的 $16\%$，其中满足 $p \le 2$。

输出格式

标准输出仅一行，包含一个整数，表示可能的排列方案数对 $10^9 + 7$ 取模后的结果。

样例

输入 1

5 2 3
1 3
5 4

输出 1

6

说明

样例解释：巫师们可以按以下六种顺序之一坐在桌旁：53124, 53142, 52143, 53412, 52314, 53214。