Guest User

D

a guest
May 19th, 2013
544
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #define _CRT_SECURE_NO_DEPRECATE  
  2. #define _SECURE_SCL 0  
  3. #pragma comment(linker, "/STACK:200000000")  
  4.  
  5. #include <algorithm>  
  6. #include <bitset>  
  7. #include <cassert>  
  8. #include <cctype>  
  9. #include <complex>  
  10. #include <ctime>  
  11. #include <cstdio>  
  12. #include <cstdlib>  
  13. #include <cstring>  
  14. #include <deque>  
  15. #include <functional>  
  16. #include <fstream>  
  17. #include <iostream>  
  18. #include <map>  
  19. #include <memory.h>  
  20. #include <numeric>  
  21. #include <iomanip>  
  22. #include <queue>  
  23. #include <set>  
  24. #include <stack>  
  25. #include <list>  
  26. #include <string>  
  27. #include <iomanip>  
  28. #include <sstream>  
  29. #include <vector>  
  30. #include <utility>  
  31. #include <cmath>  
  32. using namespace std;  
  33.  
  34. #define pb push_back  
  35. #define mp make_pair  
  36. #define mset(mas,val) memset(mas,val,sizeof(mas))  
  37. #define sz(a) (int)(a).size()  
  38. #define all(a) (a).begin(), (a).end()  
  39. #define rall(a) (a).rbegin(), (a).rend()  
  40.  
  41. #define forn(i,n) for (int i=0; i<int(n); ++i)  
  42. #define fornd(i,n) for (int i=int(n)-1; i>=0; --i)  
  43. #define forab(i,a,b) for (int i=int(a); i<int(b); ++i)  
  44.  
  45. typedef long long ll;  
  46. typedef long double ld;  
  47. typedef unsigned long long ull;  
  48.      
  49. const int INF = (int) 1e9;  
  50. const long long INF64 = (long long) 1e18;  
  51. const long double eps = 1e-9;  
  52. const long double pi = 3.14159265358979323846;  
  53.  
  54. const int MOD = INF + 7;  
  55.  
  56. ll bpow(ll val, ll deg) {  
  57.     if (deg == 0) return 1;  
  58.     if (deg & 1) {  
  59.         return (val * bpow(val, deg - 1)) % MOD;  
  60.     } else {  
  61.         ll res = bpow(val, deg >> 1);  
  62.         return (res * res) % MOD;  
  63.     }  
  64. }  
  65.  
  66. int main(){  
  67. #ifdef gridnevvvit  
  68.     freopen("input.txt","rt",stdin);  
  69.     freopen("output.txt","wt",stdout);  
  70. #endif  
  71.     int n, m, k;  
  72.     scanf("%d %d %d", &n, &m, &k);  
  73.     vector < pair<int,int> > edges(m);  
  74.     forn(i,m) {  
  75.         scanf("%d %d",&edges[i].first,&edges[i].second);  
  76.     }  
  77.  
  78.     /* next part of code checks that answer is a zero */  
  79.      
  80.     vector < pair<int,int> > tmp;  
  81.     forn(i,m) {  
  82.         if (edges[i].second - edges[i].first != 1 && edges[i].second - edges[i].first != k + 1) {  
  83.             puts("0");  
  84.             return 0;  
  85.         }  
  86.         if (edges[i].second - edges[i].first == k + 1) {  
  87.             tmp.push_back(edges[i]);  
  88.         }  
  89.     }  
  90.     edges = tmp;  
  91.     forn(i, sz(edges)) {
  92.         if (!(edges[i].first >= edges[0].first && edges[i].first < edges[0].second)) {
  93.             puts("0");
  94.             return 0;
  95.         }
  96.     }
  97.     /* k == 0 or k >= n - 1 answer one because distance between i, j equals j - i for all i, j */  
  98.     if (k == 0 || k >= n - 1) {  
  99.         puts("1");  
  100.         return 0;  
  101.     }  
  102.  
  103.     /* if (k != 0) there are two parts of formula */  
  104.      
  105.     int ans = 0;  
  106.      
  107.     /* first variant: we choose as left bound edge from the input */  
  108.      
  109.     if (sz(edges) > 0) {  
  110.         int left = edges[0].first;  
  111.         int right = edges[0].second;  
  112.         right = min(n - k, right);  
  113.         int total = right - left - 1;  
  114.         total -= (sz(edges) - 1);  
  115.         ans += bpow(2ll, total);  
  116.         if (ans >= MOD) ans -= MOD;  
  117.     } else {
  118.         ++ans;
  119.     }
  120.  
  121.     /* second variant : we choose another edge as a left bound */  
  122.      
  123.     /* there are two variants: if we have no edges, or when have one or more */  
  124.     int leftdeg = 0,  
  125.         rightdeg = 0,  
  126.         cntvalues = 0;  
  127.     if (sz(edges) == 0) {  
  128.         int left = 1;  
  129.         int rightbound = min(left + k + 1, n - k);  
  130.         leftdeg = rightbound - left - 1;  
  131.         int right = n - k - 1;  
  132.         rightbound = min(right + k + 1, n - k);  
  133.         rightdeg = rightbound - right - 1;  
  134.         cntvalues = right - left + 1;  
  135.     } else {  
  136.         if (edges[0].first != 1 && edges[sz(edges) - 1].first != edges[0].second - 1) {  
  137.             int right = edges[0].first - 1;  
  138.             int left = max(edges[sz(edges) - 1].first + 1 - k - 1, 1);  
  139.             int rightbound = min(left + k + 1, n - k);  
  140.             leftdeg = rightbound - left - 1 - sz(edges);  
  141.             rightbound = min(right + k + 1, n - k);  
  142.             rightdeg = rightbound - right - 1 - sz(edges);  
  143.             cntvalues = right - left + 1;  
  144.         }  
  145.     }  
  146.     if (cntvalues != 0) {  
  147.         int firstpart = leftdeg - rightdeg;  
  148.         if (firstpart != 0) {  
  149.             long long res = bpow(2ll, rightdeg);  
  150.             long long arithmet = bpow(2ll, firstpart);  
  151.             arithmet = (arithmet - 1 + MOD) % MOD;  
  152.             res = (res * arithmet) % MOD;  
  153.             ans += res;  
  154.             if (ans >= MOD) ans -= MOD;  
  155.             cntvalues -= firstpart;  
  156.         }  
  157.         if (cntvalues != 0) {  
  158.             long long res = bpow(2ll, leftdeg);  
  159.             res = (res * 1ll * (ll)cntvalues) % MOD;  
  160.             ans += res;  
  161.             if (ans >= MOD)  
  162.                 ans -= MOD;  
  163.         }  
  164.     }  
  165.     cout << ans << endl;  
  166. }
RAW Paste Data