#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000000 + 10;
const long long mod = 1000 * 1000 * 1000 + 7;
vector<int> v[maxn];
int n, m, k;
inline int Pow(int fi, int se) {
  if (se == 0) return 1;
  long long ret = Pow(fi, se / 2);
  ret *= ret;
  ret %= mod;
  if (se % 2 == 1) ret *= fi;
  ret %= mod;
  return ret;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin >> n >> m >> k;
  for (int i = 1; i <= m; ++i) {
    int fi, se;
    cin >> fi >> se;
    v[fi].push_back(se);
  }
  for (int i = 1; i <= n; ++i) sort(v[i].begin(), v[i].end());
  for (int i = 1; i <= n; ++i)
    if (v[i].size() == 0 || v[i][0] != i + 1) v[i].push_back(i + 1);
  for (int i = 1; i <= n; ++i) sort(v[i].begin(), v[i].end());
  for (int i = 1; i <= n; ++i)
    if (v[i].size() > 2) {
      cout << 0 << endl;
      return 0;
    } else if (v[i].size() == 2) {
      if (v[i][1] != i + k + 1) {
        cout << 0 << endl;
        return 0;
      }
    }
  int Min = 0;
  for (int i = 1; i <= n; ++i)
    if (v[i].size() == 2) {
      Min = i;
      break;
    }
  if (Min != 0) {
    for (int i = 1; i <= n; ++i)
      if (v[i].size() == 2 && i >= Min + k + 1) {
        cout << 0 << endl;
        return 0;
      }
    long long ans = 0;
    int Max = 0;
    for (int i = n; i >= 1; --i)
      if (v[i].size() == 2) {
        Max = i;
        break;
      }
    int t = 0;
    for (int i = 1; i <= n; ++i) t += (v[i].size() == 2);
    for (int i = 1; i <= n; ++i)
      if (i + k + 1 > Max && i < Min) {
        ans += Pow(2, (min(i + k, n - k - 1) - i) - t);
        ans %= mod;
      }
    ans += Pow(2, (min(Min + k, n - k - 1) - Min) - t + 1);
    ans %= mod;
    cout << ans << endl;
    return 0;
  } else {
    long long ans = 1;
    long long now = 1;
    for (int i = n - k - 1; i >= 1; --i) {
      ans += now;
      if (i > n - k - k - 1) {
        now *= 2;
        now %= mod;
      }
      ans %= mod;
    }
    cout << ans << endl;
  }
  return 0;
}
