#include <bits/stdc++.h> #define FOR(i, x, y) for (int i = x; i < y; i++) typedef long long ll; using namespace std; const ll MOD = 1e9; pair<int, int> sorted[2][100001]; vector<int> graphs[2][100001]; ll num_blocks[2][100001], dp[2][100001]; int x = 0, y = 0; map<pair<int, int>, int> x_cmp, y_cmp; int DistanceSum(int N, int *X, int *Y) { FOR(i, 0, N) { sorted[0][i] = {X[i], Y[i]}; sorted[1][i] = {Y[i], X[i]}; } sort(sorted[0], sorted[0] + N); sort(sorted[1], sorted[1] + N); FOR(i, 0, N) { if (i == 0 || sorted[0][i].second - sorted[0][i - 1].second != 1 || sorted[0][i].first != sorted[0][i - 1].first) { y++; if (y_cmp[{sorted[0][i].first - 1, sorted[0][i].second}]) graphs[0][y_cmp[{sorted[0][i].first - 1, sorted[0][i].second}]].push_back(y); } num_blocks[0][y]++; y_cmp[sorted[0][i]] = y; } FOR(i, 0, N) { if (i == 0 || sorted[1][i].second - sorted[1][i - 1].second != 1 || sorted[1][i].first != sorted[1][i - 1].first) { x++; if (x_cmp[{sorted[1][i].first - 1, sorted[1][i].second}]) graphs[1][x_cmp[{sorted[1][i].first - 1, sorted[1][i].second}]].push_back(x); } num_blocks[1][x]++; x_cmp[sorted[1][i]] = x; } ll ans = 0; FOR(i, 1, y + 1) { ans = (ans + dp[0][i]) % MOD; for (int j : graphs[0][i]) dp[0][j] = (dp[0][j] + dp[0][i] * num_blocks[0][i] + num_blocks[0][i] * num_blocks[0][j]) % MOD; } FOR(i, 1, x + 1) { ans = (ans + dp[1][i]) % MOD; for (int j : graphs[1][i]) dp[1][j] = (dp[1][j] + dp[1][i] * num_blocks[1][i] + num_blocks[1][i] * num_blocks[1][j]) % MOD; } return (int)ans; }