# AtCoder Grand Contest 001: E - BBQ Hard

,

## solution

DPで組み合せ求めるやつを同じ表でまとめてやる。 $H = \max_i A_i, \; W = \max_i B_i$として$O(HW)$。

## implementation

#include <cstdio>
#include <vector>
#include <algorithm>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
using ll = long long;
using namespace std;
template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }

constexpr int mod = 1e9+7;
int main() {
// input
int n; scanf("%d", &n);
vector<int> a(n), b(n); repeat (i,n) scanf("%d%d", &a[i], &b[i]);
// dp
int max_a = *whole(max_element, a);
int max_b = *whole(max_element, b);
vector<vector<int> > choose = vectors(2*max_a+1, 2*max_b+1, int());
choose[0][0] = 1;
vector<vector<int> > dp = vectors(2*max_a+1, 2*max_b+1, int());
repeat (i,n) {
dp[max_a-a[i]][max_b-b[i]] += 1;
}
repeat (y,2*max_a+1) {
repeat (x,2*max_b+1) {
choose[y][x] %= mod;
dp[y][x] %= mod;
if (y+1 < 2*max_a+1) choose[y+1][x] += choose[y][x];
if (x+1 < 2*max_b+1) choose[y][x+1] += choose[y][x];
if (y+1 < 2*max_a+1) dp[y+1][x] += dp[y][x];
if (x+1 < 2*max_b+1) dp[y][x+1] += dp[y][x];
}
}
// result
ll result = 0;
repeat (i,n) {
result += dp[max_a+a[i]][max_b+b[i]];
result -= choose[2*a[i]][2*b[i]];
}
result %= mod;
result *= (mod+1)/2; // inv(2, mod)
result %= mod;
if (result < 0) result += mod;
// output
printf("%lld\n", result);
return 0;
}