#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const long long mod = 1e9 + 9;
int n, start = 1;
int a[4 * N], ans[N];
vector<int> jos[N], sus[N];
map<pair<int, int>, int> m;
struct punct {
  int x, y;
} poz[N];
void Update(int nod) {
  a[nod] = max(a[nod + nod], a[nod + nod + 1]);
  if (nod > 1) Update(nod / 2);
}
void check(int poz) {
  for (auto it : sus[poz]) {
    if (jos[it].size() == 1) {
      return;
    }
  }
  a[poz + start - 1] = 1;
  Update((poz + start - 1) / 2);
}
void REMOVE(int poz) {
  for (auto it : jos[poz]) {
    for (int i = 0; i < sus[it].size(); ++i) {
      if (sus[it][i] == poz) {
        sus[it].erase(sus[it].begin() + i);
        break;
      }
    }
    check(it);
  }
  for (auto it : sus[poz]) {
    for (int i = 0; i < jos[it].size(); ++i) {
      if (jos[it][i] == poz) {
        jos[it].erase(jos[it].begin() + i);
        break;
      }
    }
    if (jos[it].size() == 1) {
      a[jos[it][0] + start - 1] = 0;
      Update((jos[it][0] + start - 1) / 2);
    }
  }
  a[poz + start - 1] = 0;
  Update((poz + start - 1) / 2);
}
int find_left() {
  int nod = 1;
  while (nod < start) {
    if (a[nod + nod] >= a[nod + nod + 1])
      nod = nod + nod;
    else
      nod = nod + nod + 1;
  }
  return nod;
}
int find_right() {
  int nod = 1;
  while (nod < start) {
    if (a[nod + nod + 1] >= a[nod + nod])
      nod = nod + nod + 1;
    else
      nod = nod + nod;
  }
  return nod;
}
int main() {
  cin >> n;
  while (start < n) start <<= 1;
  for (int i = 1; i <= n; ++i) {
    cin >> poz[i].x >> poz[i].y;
    m[{poz[i].x, poz[i].y}] = i;
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = -1; j <= 1; ++j) {
      if (m[{poz[i].x + j, poz[i].y - 1}]) {
        jos[i].push_back(m[{poz[i].x + j, poz[i].y - 1}]);
        sus[m[{poz[i].x + j, poz[i].y - 1}]].push_back(i);
      }
    }
    a[i + start - 1] = 1;
    Update((i + start - 1) / 2);
  }
  for (int i = 1; i <= n; ++i) {
    if (jos[i].size() == 1) {
      a[jos[i][0] + start - 1] = 0;
      Update((jos[i][0] + start - 1) / 2);
    }
  }
  int poz = 0;
  for (int i = 1; i <= n; ++i) {
    if (i & 1) {
      poz = find_right();
    } else
      poz = find_left();
    poz = poz - start + 1;
    REMOVE(poz);
    ans[i] = poz;
  }
  long long r = 0, P = 1;
  for (int i = n; i; --i) {
    r += ((long long)(ans[i] - 1) * P) % mod;
    r %= mod;
    P = (P * (long long)n) % mod;
  }
  cout << r;
  return 0;
}
