Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include <iostream>
- #include <vector>
- #include <string>
- #include <algorithm>
- #include <set>
- #include <map>
- #include <cmath>
- #include <queue>
- #include <iomanip>
- #include <bitset>
- #include <unordered_map>
- #include <stack>
- #include <memory.h>
- #include <list>
- #include <numeric>
- #include <functional>
- #include <complex>
- #include <cassert>
- #include <regex>
- #include <random>
- #include <unordered_set>
- #include <numeric>
- using namespace std;
- #define x first
- #define y second
- typedef pair<int, int> pt;
- typedef long double ld;
- typedef long long ll;
- typedef unsigned long long ull;
- #define all(x) (x).begin(),(x).end()
- #define rall(x) (x).rbegin(),(x).rend()
- const int M = (int)1e3 + 5;
- const int N = (int)1e6 + 5;
- const int mod = (int)1e9 + 7;
- int add(int a, int b) {
- a += b;
- if (a >= mod) a -= mod;
- if (a < 0) a += mod;
- return a;
- }
- int sub(int a, int b) {
- return add(a, -b);
- }
- int mul(int a, int b) {
- return (int)((ll)a * b % mod);
- }
- int binpow(int a, int n) {
- int res = 1;
- while (n > 0) {
- if (n & 1) {
- res = mul(res, a);
- }
- a = mul(a, a);
- n >>= 1;
- }
- return res;
- }
- int inv(int x) {
- return binpow(x, mod - 2);
- }
- int f[N];
- int invf[N];
- void precalc() {
- f[0] = 1;
- for (int i = 1; i < N; i++) {
- f[i] = mul(f[i - 1], i);
- }
- invf[N - 1] = inv(f[N - 1]);
- for (int i = N - 2; i >= 0; i--) {
- invf[i] = mul(invf[i + 1], i + 1);
- }
- }
- int binom(int n, int k) {
- return mul(f[n],
- mul(invf[k], invf[n - k]));
- }
- int bad[M];
- int main() {
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #else
- //freopen("sum.in", "r", stdin);
- //freopen("sum.out", "w", stdout);
- //freopen("input.txt", "r", stdin);
- //freopen("output.txt", "w", stdout);
- #endif
- ios::sync_with_stdio(false);
- cin.tie(0); cout.tie(0);
- precalc();
- int n, m;
- cin >> n >> m;
- vector<pt>p(m);
- for (int i = 0; i < m; i++) {
- cin >> p[i].y >> p[i].x;
- }
- sort(all(p), [](pt p1, pt p2) {
- if (p1.y != p2.y) return p1.y < p2.y;
- return p1.x < p2.x;
- });
- int ans = binom(2 * (n - 1), n - 1);
- for (int i = 0; i < m; i++) {
- bad[i] = binom(p[i].x + p[i].y - 2, p[i].x - 1);
- for (int j = 0; j < i; j++) {
- if (p[j].y > p[i].y || p[j].x > p[i].x) continue;
- int dy = p[i].y - p[j].y + 1;
- int dx = p[i].x - p[j].x + 1;
- bad[i] = sub(bad[i], mul(bad[j], binom(dy + dx - 2, dx - 1)));
- }
- int dy = n - p[i].y + 1;
- int dx = n - p[i].x + 1;
- ans = sub(ans, mul(bad[i], binom(dy + dx - 2, dx - 1)));
- }
- cout << ans;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement