Advertisement
Guest User

Untitled

a guest
Sep 16th, 2019
78
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.58 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <iostream>
  3. #include <vector>
  4. #include <string>
  5. #include <algorithm>
  6. #include <set>
  7. #include <map>
  8. #include <cmath>
  9. #include <queue>
  10. #include <iomanip>
  11. #include <bitset>
  12. #include <unordered_map>
  13. #include <stack>
  14. #include <memory.h>
  15. #include <list>
  16. #include <numeric>
  17. #include <functional>
  18. #include <complex>
  19. #include <cassert>
  20. #include <regex>
  21. #include <random>
  22. #include <unordered_set>
  23. #include <numeric>
  24.  
  25. using namespace std;
  26.  
  27. #define x first
  28. #define y second
  29. typedef pair<int, int> pt;
  30. typedef long double ld;
  31. typedef long long ll;
  32. typedef unsigned long long ull;
  33. #define all(x) (x).begin(),(x).end()
  34. #define rall(x) (x).rbegin(),(x).rend()
  35.  
  36.  
  37. const int M = (int)1e3 + 5;
  38. const int N = (int)1e6 + 5;
  39. const int mod = (int)1e9 + 7;
  40.  
  41. int add(int a, int b) {
  42.     a += b;
  43.     if (a >= mod) a -= mod;
  44.     if (a < 0) a += mod;
  45.     return a;
  46. }
  47.  
  48. int sub(int a, int b) {
  49.     return add(a, -b);
  50. }
  51.  
  52. int mul(int a, int b) {
  53.     return (int)((ll)a * b % mod);
  54. }
  55.  
  56. int binpow(int a, int n) {
  57.     int res = 1;
  58.  
  59.     while (n > 0) {
  60.         if (n & 1) {
  61.             res = mul(res, a);
  62.         }
  63.  
  64.         a = mul(a, a);
  65.         n >>= 1;
  66.     }
  67.  
  68.     return res;
  69. }
  70.  
  71. int inv(int x) {
  72.     return binpow(x, mod - 2);
  73. }
  74.  
  75. int f[N];
  76. int invf[N];
  77.  
  78. void precalc() {
  79.     f[0] = 1;
  80.     for (int i = 1; i < N; i++) {
  81.         f[i] = mul(f[i - 1], i);
  82.     }
  83.  
  84.     invf[N - 1] = inv(f[N - 1]);
  85.  
  86.     for (int i = N - 2; i >= 0; i--) {
  87.         invf[i] = mul(invf[i + 1], i + 1);
  88.     }
  89. }
  90.  
  91. int binom(int n, int k) {
  92.     return mul(f[n],
  93.         mul(invf[k], invf[n - k]));
  94. }
  95.  
  96. int bad[M];
  97.  
  98. int main() {
  99. #ifdef _DEBUG
  100.     freopen("input.txt", "r", stdin);
  101.     freopen("output.txt", "w", stdout);
  102. #else
  103.     //freopen("sum.in", "r", stdin);
  104.     //freopen("sum.out", "w", stdout);
  105.     //freopen("input.txt", "r", stdin);
  106.     //freopen("output.txt", "w", stdout);
  107. #endif
  108.     ios::sync_with_stdio(false);
  109.     cin.tie(0); cout.tie(0);
  110.     precalc();
  111.     int n, m;
  112.     cin >> n >> m;
  113.  
  114.     vector<pt>p(m);
  115.     for (int i = 0; i < m; i++) {
  116.         cin >> p[i].y >> p[i].x;
  117.     }
  118.  
  119.     sort(all(p), [](pt p1, pt p2) {
  120.         if (p1.y != p2.y) return p1.y < p2.y;
  121.         return p1.x < p2.x;
  122.     });
  123.  
  124.     int ans = binom(2 * (n - 1), n - 1);
  125.  
  126.     for (int i = 0; i < m; i++) {
  127.         bad[i] = binom(p[i].x + p[i].y - 2, p[i].x - 1);
  128.  
  129.         for (int j = 0; j < i; j++) {
  130.             if (p[j].y > p[i].y || p[j].x > p[i].x) continue;
  131.             int dy = p[i].y - p[j].y + 1;
  132.             int dx = p[i].x - p[j].x + 1;
  133.             bad[i] = sub(bad[i], mul(bad[j], binom(dy + dx - 2, dx - 1)));
  134.         }
  135.  
  136.         int dy = n - p[i].y + 1;
  137.         int dx = n - p[i].x + 1;
  138.         ans = sub(ans, mul(bad[i], binom(dy + dx - 2, dx - 1)));
  139.     }
  140.  
  141.     cout << ans;
  142.     return 0;
  143. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement