#include <bits/stdc++.h>
using namespace std;
int pw[1000100];
int jmp[1000100];
int n, m, k;
int main() {
  pw[0] = 1;
  for (int i = 1; i < 1000100; ++i) pw[i] = (pw[i - 1] << 1) % 1000000007;
  bool ok = true;
  int ans = 0;
  int min_start = 1000100;
  int max_start = 0;
  int long_edge = 0;
  scanf("%i %i %i", &n, &m, &k);
  k++;
  for (int i = 0; i < m; ++i) {
    int x, y;
    scanf("%i %i", &x, &y);
    if (x > y) swap(x, y);
    ok = ok && (x + 1 == y || x + k == y);
    if (x + k == y) {
      min_start = min(min_start, x);
      max_start = max(max_start, x);
      long_edge++;
      jmp[x] = 1;
    }
  }
  if (long_edge) {
    ok = ok && (min_start + k > max_start);
    for (int i = 1; i + k <= n; ++i)
      if (i + k > max_start && i <= min_start) {
        int cnt = 0;
        int j = n - k;
        if (j < i + k)
          cnt = j - i + 1;
        else
          cnt = k;
        cnt -= long_edge;
        if (!jmp[i]) cnt--;
        ans = (ans + pw[cnt]) % 1000000007;
      }
  } else {
    ans++;
    for (int i = 1; i + k <= n; ++i) {
      int cnt = 0;
      int j = n - k;
      if (j < i + k)
        cnt = j - i;
      else
        cnt = k - 1;
      ans = (ans + pw[cnt]) % 1000000007;
    }
  }
  if (!ok) ans = 0;
  printf("%i\n", ans);
}
