Submission #3054787

---

Source Code Expand

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int   N   = 2001;
const int   mod = 1e9 + 7;

void add(int &a,int b)  {
    a += b;
    if(a >= mod)a -= mod;
    if(a < 0)   a += mod;
}
int qpow(int a,int exp) {
    int ans = 1;
    while(exp)  {
        if(exp & 1) ans = ans * a % mod;
        a = a * a % mod;  exp >>= 1;
    }
    return ans;
}

int upd[N * 2][N * 2];
int Fac[N * 2];
int Inv[N * 2];

vector<int> Q[N * 2];

signed main()   {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    Fac[0] = Inv[0] = 1;
    for(int i = 1 ; i < N * 2 ; ++i)
        Fac[i] = Fac[i - 1] * i % mod,
        Inv[i] = Inv[i - 1] * qpow(i,mod - 2) % mod;

    int n;  cin >> n;
    int ans = 0;

    while(n--)  {
        int x, y;   cin >> x >> y;
        upd[N - x][N - y]++;
        Q[N + x].push_back(N + y);
        int res = Fac[2 * x + 2 * y];
            res = res * Inv[2 * x] % mod;
            res = res * Inv[2 * y] % mod;
        add(ans,-res);
    }

    for(int i = 1 ; i < 2 * N ; ++i)    {
        for(int j = 1 ; j < 2 * N ; ++j)
            add(upd[i][j],upd[i][j - 1]),
            add(upd[i][j],upd[i - 1][j]);
        for(int y : Q[i])
            add(ans,upd[i][y]);
    }

    cout << ans * 500000004ll % mod << endl;
}

Submission Info

Judge Result