#include <bits/stdc++.h>
using namespace std;
long long rdtsc() {
  long long tmp;
  asm("rdtsc" : "=A"(tmp));
  return tmp;
}
inline int myrand() { return abs((rand() << 15) ^ rand()); }
inline int rnd(int x) { return myrand() % x; }
const int MOD = (int)1e9 + 7;
inline void add(int &x, int y) {
  if ((x += y) >= MOD) x -= MOD;
}
const int maxn = (int)1e6 + 10;
int two[maxn];
void precalc() {
  two[0] = 1;
  for (int i = 1; i < maxn; ++i) two[i] = two[i - 1], add(two[i], two[i]);
}
bool solve() {
  int n, m, k;
  if (scanf("%d%d%d", &n, &m, &k) < 3) return 0;
  vector<int> a;
  bool fail = false;
  for (int i = 0; i < m; ++i) {
    int s, t;
    scanf("%d%d", &s, &t);
    --s, --t;
    if (t - s != 1) {
      if (t - s != (k + 1)) {
        fail = true;
      } else {
        a.push_back(s);
      }
    }
  }
  if (fail) {
    printf("0\n");
    return 1;
  }
  sort(a.begin(), a.end());
  int ans = 0;
  for (int i = 0; i < n; ++i) {
    if (((int)(a).size()) && i > a[0]) break;
    int right = min(n - 2 - k, i + k);
    if (((int)(a).size()) && a[((int)(a).size()) - 1] > right) continue;
    if (right < i) continue;
    int places = right - i + 1 - ((int)(a).size());
    if (!((int)(a).size()) || a[0] != i) places -= 1;
    add(ans, two[places]);
  }
  if (!((int)(a).size())) add(ans, 1);
  printf("%d\n", ans);
  return 1;
}
int main() {
  srand(rdtsc());
  precalc();
  while (1) {
    if (!solve()) break;
  }
  return 0;
}
