#include <bits/stdc++.h>
int n, m, k, flag, ans, cnt, p, q, w[1000005], f[1000005], g[1000005],
    s[1000005];
int main() {
  scanf("%d%d%d", &n, &m, &k);
  w[0] = 1;
  for (int i = 1; i <= n; i++) w[i] = w[i - 1] * 2 % 1000000007;
  for (int i = 1; i <= m; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    if (x > y) std::swap(x, y);
    if (x + 1 == y)
      f[x] = 1;
    else if (x + k + 1 == y)
      g[x] = 1, ++cnt;
    else
      flag = 1;
  }
  if (flag) {
    puts("0");
    return 0;
  }
  if (cnt == 0) {
    for (int i = 1; i <= n; i++) {
      if (i + k + 1 > n) continue;
      int up = (i + k + k + 1 > n ? n - k - 1 : i + k);
      int can = up - i + 1;
      ans = (ans + w[can - 1]) % 1000000007;
    }
    ++ans;
    printf("%d\n", ans);
    return 0;
  }
  for (int i = 1; i <= n; i++)
    if (g[i]) q = i;
  for (int i = n; i >= 1; i--)
    if (g[i]) p = i;
  if (p + k + 1 <= q) {
    puts("0");
    return 0;
  }
  for (int i = 1; i <= n; i++) s[i] = s[i - 1] + g[i];
  for (int i = 1; i <= n; i++) {
    if (g[i] || i + k + 1 > n) continue;
    if (i >= p + k + 1 || i + k + 1 <= q) continue;
    int cp = p, cq = q;
    if (i < p) p = i;
    if (i > q) q = i;
    int up = (p + k + k + 1 > n ? n - k - 1 : p + k);
    int can = up - i + 1 - (s[up] - s[i - 1]);
    ans = (ans + w[can - 1]) % 1000000007;
    q = cq, p = cp;
  }
  ++ans;
  printf("%d\n", ans);
}
