#include <bits/stdc++.h>
using namespace std;
long long mod = 1e9 + 9;
map<pair<int, int>, int> M;
map<int, pair<int, int> > P;
vector<int> V;
set<int> S;
long long power(long long a, long long b) {
  long long ret = 1;
  while (b) {
    if (b % 2) ret *= a, ret %= mod;
    b >>= 1, a *= a, a %= mod;
  }
  return ret;
}
bool valid(int i) {
  int x = P[i].first, y = P[i].second;
  bool flag1 = true, flag2 = true, flag3 = true;
  if (M.count(pair<int, int>(x + 1, y + 1))) {
    if (!M.count(pair<int, int>(x + 1, y)) &&
        !M.count(pair<int, int>(x + 2, y)))
      flag1 = false;
  }
  if (M.count(pair<int, int>(x, y + 1))) {
    if (!M.count(pair<int, int>(x + 1, y)) &&
        !M.count(pair<int, int>(x - 1, y)))
      flag1 = false;
  }
  if (M.count(pair<int, int>(x - 1, y + 1))) {
    if (!M.count(pair<int, int>(x - 1, y)) &&
        !M.count(pair<int, int>(x - 2, y)))
      flag1 = false;
  }
  return flag1 && flag2 && flag3;
}
void edit(int i) {
  int x = P[i].first, y = P[i].second;
  if (M.count(pair<int, int>(x + 1, y)) && V[M[pair<int, int>(x + 1, y)]] &&
      !valid(M[pair<int, int>(x + 1, y)])) {
    S.erase(M[pair<int, int>(x + 1, y)]);
    V[M[pair<int, int>(x + 1, y)]] = false;
  }
  if (M.count(pair<int, int>(x + 2, y)) && V[M[pair<int, int>(x + 2, y)]] &&
      !valid(M[pair<int, int>(x + 2, y)])) {
    S.erase(M[pair<int, int>(x + 2, y)]);
    V[M[pair<int, int>(x + 2, y)]] = false;
  }
  if (M.count(pair<int, int>(x - 1, y)) && V[M[pair<int, int>(x - 1, y)]] &&
      !valid(M[pair<int, int>(x - 1, y)])) {
    S.erase(M[pair<int, int>(x - 1, y)]);
    V[M[pair<int, int>(x - 1, y)]] = false;
  }
  if (M.count(pair<int, int>(x - 2, y)) && V[M[pair<int, int>(x - 2, y)]] &&
      !valid(M[pair<int, int>(x - 2, y)])) {
    S.erase(M[pair<int, int>(x - 2, y)]);
    V[M[pair<int, int>(x - 2, y)]] = false;
  }
  if (M.count(pair<int, int>(x - 1, y - 1)) &&
      valid(M[pair<int, int>(x - 1, y - 1)])) {
    S.insert(M[pair<int, int>(x - 1, y - 1)]);
    V[M[pair<int, int>(x - 1, y - 1)]] = true;
  }
  if (M.count(pair<int, int>(x, y - 1)) && valid(M[pair<int, int>(x, y - 1)])) {
    S.insert(M[pair<int, int>(x, y - 1)]);
    V[M[pair<int, int>(x, y - 1)]] = true;
  }
  if (M.count(pair<int, int>(x + 1, y - 1)) &&
      valid(M[pair<int, int>(x + 1, y - 1)])) {
    S.insert(M[pair<int, int>(x + 1, y - 1)]);
    V[M[pair<int, int>(x + 1, y - 1)]] = true;
  }
}
int main() {
  int N;
  cin >> N;
  V.assign(N, 1);
  for (int i = 0; i < N; ++i) {
    int x, y;
    cin >> x >> y;
    M[pair<int, int>(x, y)] = i;
    P[i] = pair<int, int>(x, y);
  }
  for (int i = 0; i < N; ++i) {
    V[i] = valid(i);
    if (V[i]) S.insert(i);
  }
  bool maxi = true;
  int pos = 0;
  set<int>::iterator it;
  long long ans = 0;
  for (int i = 0; i < N; ++i) {
    if (maxi) {
      it = S.end();
      it--;
      pos = *it;
      ans += (pos)*power(N, N - i - 1);
      ans %= mod;
      M.erase(P[pos]);
      edit(pos);
      V[pos] = 0;
      S.erase(pos);
      maxi = false;
    } else {
      it = S.begin();
      pos = *it;
      ans += (pos)*power(N, N - i - 1);
      ans %= mod;
      M.erase(P[pos]);
      edit(pos);
      V[pos] = 0;
      S.erase(pos);
      maxi = true;
    }
  }
  cout << ans << "\n";
}
