Pagini recente » Cod sursa (job #1356419) | Cod sursa (job #2168544) | Cod sursa (job #1696692) | Cod sursa (job #1276534) | Cod sursa (job #2435337)
#include <bits/stdc++.h>
#define mod 1000000007
using namespace std;
typedef long long ll;
typedef long double ld;
ll n, m, k, A[1005], F[2000005];
pair<ll, ll> V[1005];
void gcd(ll &x, ll &y, ll a, ll b)
{
if (!b)
x = 1, y = 0;
else
{
gcd(x, y, b, a % b);
ll aux = x;
x = y;
y = aux - y * (a / b);
}
}
ll inv(ll A)
{
ll inv=0, ins;
gcd(inv, ins, A, mod);
if (inv <= 0)
inv = mod + inv % mod;
return inv % mod;
}
ll solve(ll x, ll y)
{
return ((F[x+y-2] * inv(F[y-1]) %mod) * inv(F[x-1])) % mod;
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
freopen("padure2.in", "r", stdin);
freopen("padure2.out", "w", stdout);
cin>>n>>m>>k;
F[0]=1;
for (int i=1; i<=2e6; i++)
F[i] = (F[i-1]*i)%mod;
ll sol = solve(n, m);
for (int i=1; i<=k; i++)
{
cin>>V[i].first>>V[i].second;
}
sort(V+1, V+k+1);
for (int i=1; i<=k; i++)
A[i] = solve(V[i].first, V[i].second);
for (int i=1; i<=k; i++)
{
sol -= solve(n-V[i].first+1, m-V[i].second+1) * A[i] % mod;
sol %= mod;
if (sol < 0)
sol+=mod;
for (int j=i+1; j<=k; j++)
{
if (V[i].second>V[j].second) continue;
A[j] -= solve(abs(V[i].first-V[j].first)+1, abs(V[i].second-V[j].second)+1) * A[i] %mod;
A[j] %= mod;
if (A[j]<0)
A[j]+=mod;
}
}
cout<<sol;
return 0;
}