#include #define endl '\n' #define fi first #define se second using namespace std; void fileIO() { freopen("feetS.in", "r", stdin); freopen("feetS.out", "w", stdout); } void fastIO() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); } const int MAXN=2e6+5; const int MAXQ=3005; const int MOD=77726557; int n,m,q; int dp[2][MAXQ]; pair p[MAXQ]; int N; int fact[MAXN]; int invFact[MAXN]; int fastPow(long long x,int pwr) { long long ret=1; while(pwr) { if(pwr&1) ret=ret*x%MOD; pwr/=2; x=x*x%MOD; } return ret; } int inv(int x) { return fastPow(x,MOD-2); } int comb(int n,int k) { return (1LL*fact[n]*invFact[n-k]%MOD)*invFact[k]%MOD; } void precomp() { N=n+m; fact[0]=1; for(int i=1;i<=N;i++) fact[i]=1LL*fact[i-1]*i%MOD; for(int i=0;i<=N;i++) invFact[i]=inv(fact[i]); } int ways(int x1,int y1,int x2,int y2) { int dx=x2-x1; int dy=y2-y1; return comb(dx+dy,dx); } void solve() { cin>>n>>m>>q; precomp(); for(int i=1;i<=q;i++) { cin>>p[i].fi>>p[i].se; } sort(p+1,p+q+1); for(int i=1;i<=q;i++) dp[0][i]=ways(1,1,p[i].fi,p[i].se); for(int i=1;i<=q;i++) { for(int j=i-1;j>=1;j--) { if(p[j].fi<=p[i].fi && p[j].se<=p[i].se) dp[0][i]=(dp[0][i]-(1LL*dp[0][j]*ways(p[j].fi,p[j].se,p[i].fi,p[i].se)%MOD)+MOD)%MOD; } } for(int i=1;i<=q;i++) dp[1][i]=ways(p[i].fi,p[i].se,n,m); for(int i=q;i>=1;i--) { for(int j=i+1;j<=q;j++) { if(p[j].fi>=p[i].fi && p[j].se>=p[i].se) dp[1][i]=(dp[1][i]-(1LL*dp[1][j]*ways(p[i].fi,p[i].se,p[j].fi,p[j].se)%MOD)+MOD)%MOD; } } //for(int i=1;i<=q;i++) cout<