Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- #include <vector>
- using namespace std;
- const int MOD = 1000000007;
- const int valMax = 2 * 100005;
- long long fact[valMax];
- long long power(long long base, long long exp)
- {
- if(exp == 0)
- return 1;
- if(exp % 2 == 0)
- {
- long long x = power(base, exp / 2);
- return (x * x) % MOD;
- }
- return (base * power(base, exp - 1)) % MOD;
- }
- inline long long invers(long long x)
- {
- return power(x, MOD - 2);
- }
- void CalcFact()
- {
- fact[0] = 1;
- for(int i = 1; i < valMax; ++i)
- fact[i] = (fact[i-1] * i) % MOD;
- }
- long long comb(long long n, long long k)
- {
- return (fact[n] * invers((fact[k] * fact[n-k]) % MOD)) % MOD;
- }
- inline long long Paths(int x, int y) //drumuri de la 1,1 la x,y
- {
- return comb(x + y - 2, x - 1);
- }
- int main()
- {
- CalcFact();
- int h, w, n;
- cin >> h >> w >> n;
- vector<pair<int, int> > black(n);
- for(int i = 0; i < n; ++i)
- cin >> black[i].first >> black[i].second;
- n++;
- black.push_back(make_pair(h, w));
- sort(black.begin(), black.end());
- vector<long long> dp(n);
- dp[0] = Paths(black[0].first, black[0].second);
- for(int i = 1; i < n; ++i)
- {
- dp[i] = Paths(black[i].first, black[i].second);
- for(int j = 0; j < i; ++j)
- {
- dp[i] -= (dp[j] * Paths(black[i].first - black[j].first + 1, black[i].second - black[j].second + 1)) % MOD;
- if(dp[i] < 0)
- dp[i] += MOD;
- }
- }
- cout << dp.back();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement