#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
const long long int MOD = 1e9 + 9;
long long int powl(long long int a, long long int b) {
  long long int res = 1LL;
  if (!b) return res;
  if (b % 2) res = a;
  return (res * powl((a * a) % MOD, b / 2)) % MOD;
}
int main(void) {
  int m;
  map<pair<int, int>, int> cubes;
  map<int, pair<int, int> > free;
  cin >> m;
  for (int i = 0; i < (int)(m); i++) {
    int x, y;
    cin >> x >> y;
    cubes[pair<int, int>(x, y)] = i;
  }
  for (__typeof((cubes).begin()) e = (cubes).begin(); e != (cubes).end(); ++e) {
    int f = 0;
    pair<int, int> c = (*e).first;
    c.second++;
    for (int j = 0; j < (int)(3); j++) {
      int cnt = 0;
      pair<int, int> d = c;
      d.first += j - 1;
      if (cubes.count(d)) {
        for (int k = 0; k < (int)(3); k++) {
          pair<int, int> e = d;
          e.second--;
          e.first += k - 1;
          if (cubes.count(e)) cnt++;
        }
        if (cnt == 1) f = 1;
      }
    }
    if (!f) free[(*e).second] = (*e).first;
  }
  vector<int> ans(m);
  for (int i = 0; i < (int)(m); i++) {
    map<int, pair<int, int> >::iterator it;
    map<int, pair<int, int> >::reverse_iterator itr;
    int x;
    pair<int, int> y;
    if (!(i % 2)) {
      itr = free.rbegin();
      x = (*itr).first;
      y = (*itr).second;
    } else {
      it = free.begin();
      x = (*it).first;
      y = (*it).second;
    }
    ans[i] = x;
    free.erase(x);
    cubes.erase(y);
    for (int i = 0; i < (int)(5); i++) {
      int f = 0;
      pair<int, int> c = y;
      c.first += (i - 2);
      if (!cubes.count(c)) continue;
      for (int j = 0; j < (int)(3); j++) {
        int cnt = 0;
        pair<int, int> d = c;
        d.second++;
        d.first += (j - 1);
        if (!cubes.count(d)) continue;
        for (int k = 0; k < (int)(3); k++) {
          pair<int, int> e = d;
          e.second--;
          e.first += (k - 1);
          if (cubes.count(e)) cnt++;
        }
        if (cnt == 1) f = 1;
      }
      if (f == 1) {
        free.erase(cubes[c]);
      }
    }
    for (int i = 0; i < (int)(3); i++) {
      pair<int, int> c = y;
      c.first += (i - 1);
      c.second--;
      if (!cubes.count(c)) continue;
      int f = 0;
      for (int j = 0; j < (int)(3); j++) {
        pair<int, int> d = c;
        d.first += (j - 1);
        d.second++;
        if (cubes.count(d)) {
          int dd = 0;
          for (int k = 0; k < (int)(3); k++) {
            pair<int, int> e = d;
            e.first += (k - 1);
            e.second--;
            if (cubes.count(e)) dd++;
          }
          if (dd == 1) f = 1;
        }
      }
      if (!f) {
        free[cubes[c]] = c;
      }
    }
  }
  long long int res = 0;
  for (int i = 0; i < ans.size(); i++) {
    int id = m - i - 1;
    (res += powl((long long int)m, (long long int)i) * ans[id]) %= MOD;
  }
  cout << res << endl;
  return 0;
}
