Pagini recente » Cod sursa (job #2032190) | Cod sursa (job #2882918) | Cod sursa (job #1348002) | Cod sursa (job #2580965) | Cod sursa (job #1709282)
# include <bits/stdc++.h>
using namespace std;
# define x first
# define y second
# define fi cin
# define fo cout
# define ll long long
const int mod = 1e9 + 7;
ll dp[6005];
pair < int , int > s[6005];
ll f[1 << 20];
ll c[1 << 20];
ll pw(ll a,ll b)
{
ll ans = 1;
while (b)
{
if (b&1) ans = (ans * a) % mod;
a = (a * a) % mod;
b >>= 1;
}
return ans;
}
ll C(ll a,ll b)
{
// cout << a << ' ' << b << '\n';
// cout << f[b] << ' ' << c[a] << ' ' << c[b-a] << '\n';
return (((f[b] * c[a]) % mod) * c[b - a]) % mod;
}
int main(void)
{
ifstream fi("padure2.in");
ofstream fo("padure2.out");
int h,w,n;
fi>>h>>w>>n;
for (int i = 1;i <= n;++i) fi>>s[i].x>>s[i].y;
sort(s+1,s+1+n);
s[++n] = make_pair(h,w);
f[0] = 1;
c[0] = 1;
for (int i = 1;i <= 1e6;++i)
{
f[i] = (i * f[i-1]) % mod;
}
const int N = 1e6;
c[N] = pw(f[N],mod-2);
for (int i = N - 1;i;--i)
c[i] = (c[i+1] * (i+1)) % mod;
for (int i = 1;i <= n;++i)
{
dp[i] = C(s[i].x - 1,s[i].x + s[i].y - 2);
// cout << s[i].x << ' ' << s[i].y << ' ' << dp[i] << '\n';
for (int j = i - 1;j;--j)
if (s[j].x <= s[i].x && s[j].y <= s[i].y)
{
ll p = C(s[i].x - s[j].x,s[i].x + s[i].y - s[j].x - s[j].y);
p *= dp[j];
p %= mod;
dp[i] -= p;
if (dp[i] < 0) dp[i] += mod;
}
// cout << s[i].x << ' ' << s[i].y << ' ' << dp[i] << '\n';
dp[i] %= mod;
}
// cout << "\n\n";
return fo << dp[n] << '\n',0;
}