#include using namespace std; typedef long long int ll; typedef unsigned long long int ull; typedef vector vs; typedef vector vi; typedef vector vll; typedef vector > vvi; #define PB push_back #define PF push_front #define MP make_pair #define F first #define S second #define SZ(x) ((int)(x).size()) #define MOD(x,y) (((x%M)*(y%M))%M) ll M=1e9+7; const double INF = 1e10; /*-------------------------End----------------------------*/ const ll MAXL = 4e6+5; ll fact[MAXL],inverse[MAXL]; ll dp[5005],c; vector< pair > blocked; ll xpowy(ll x, ll y, ll mod) { ll ans = 1; while (y) { if(y&1) { ans *= x; if(ans > mod) ans %= mod; } x *= x; if(x > mod) x %= mod; y>>=1; } return ans; } ll modularInverse(ll x, ll y) { //(1/x)%y = x^(y-2) % y; return xpowy(x,y-2,y); } void precompute() { fact[0] = 1; for(int i = 1; i < MAXL; ++i) fact[i] = (i * fact[i-1]) % M; inverse[MAXL-1] = modularInverse(fact[MAXL -1], M); for(int i = MAXL - 2; i >= 0LL; --i) inverse[i] = (inverse[i+1] * (i + 1)) % M; } ll unrestrictedWays(ll x1, ll y1, ll x2, ll y2) { //ways from 1 to 2 if(x1 > x2 || y1 > y2) return 0LL; ll ans = fact[x2-x1 + y2-y1]; ans = (ans * inverse[x2-x1]) % M; ans = (ans * inverse[y2-y1]) % M; return ans; } ll restrictedWays(ll x1, ll y1, ll x2, ll y2) { //ways considering the threshold constraint //reflected coordinates in line x = y + c - 1 ll xref = y1 + (c - 1), yref = x1 - (c - 1); ll ans = (unrestrictedWays(x1, y1, x2, y2) - unrestrictedWays(xref, yref, x2, y2) + M) % M; return ans; } int main() { ll i,j,p,q,m,x,y; cin >> p >> q >> c >> m; precompute(); bool impossible = (p < q + c); for(i = 0; i < m; ++i) { cin >> x >> y; if((x >= y + c) && (x <= p && y <= q)) blocked.PB(MP(x,y)); if(y == 0 && x <= c) impossible = true; //if not able to reach (c,0) then it's not possible } blocked.PB(MP(p,q)); if(impossible) { cout << "0\n"; } else { sort(blocked.begin(), blocked.end()); /*starting point of the search is (c,0)*/ for(i = 0; i < blocked.size(); ++i) { //dp[i] stores number of valid ways of reaching ith point //considering threshold condition & if none of the points are blocked. dp[i] = restrictedWays(c, 0, blocked[i].F, blocked[i].S); } for(i = 0; i < blocked.size(); ++i) { for(j = i-1; j >= 0; --j) { if(blocked[i].F >= blocked[j].F && blocked[i].S >= blocked[j].S) { dp[i] = dp[i] - (dp[j] * restrictedWays(blocked[j].F, blocked[j].S, blocked[i].F, blocked[i].S)) % M; dp[i] = (dp[i] + M) % M; } } } cout << dp[blocked.size() - 1] << '\n'; } return 0; }