余神有一张n 个点、m 条边的有向无权图，所有点从1 到n 标号。
现在余神 想知道有多少种添加有向边的方案（可不添加），使得该图满足下列条件：
1、从点i 出发，可以到达点i+1，i+2,…..,n。
2、任意从u 到v 的有向边满足不等式：u3、两点之间最多有一条边。
4、对于一对点i、j(i5、对于一对点i、j(ik，那么从i 到j 的最短距离等于j-i 或j-i-k。

我们认为两种添加边的方案不同，当且仅当存在至少一对点i、j(i帮助余神！

由于要求的答案可能太大，将答案对1000000007 取模后输出。

第一行包含三个用空格隔开的整数，n,m,k。接下来m 行描述原图的有向边。

第i 行包含一对用空格隔开的整数ui,vi，表示第i 条有向边从ui 连向vi。

输出一个整数，即答案模1000000007。

单组数据,保证输入中任意一对点ui,vi 之间最多有一条边。

并且保证输入中给出的ui 不下降。

如果有多条有向边从ui 出发，那么这些边将按照vi 升序给出。

保证原图中任意从u 到v的有向边满足不等式：u

对于100%的数据，2<=n<=10^6,0<=m<=10^5,1<=k<=10^6。