#include <bits/stdc++.h>
using namespace std;
const int INF = (int)2e9;
const long long INFL = (long long)9e18;
const int MAXINT = ((~0) ^ (1 << 31));
const long long MAXLL = ((~0) ^ ((long long)1 << 63));
template <class T>
inline T pow2(T a) {
  return a * a;
}
template <class T>
inline bool mineq(T& a, T b) {
  return (a > b) ? (a = b, true) : false;
}
template <class T>
inline bool maxeq(T& a, T b) {
  return (a < b) ? (a = b, true) : false;
}
const int maxn = (int)1e5 + 10;
;
const int MOD = (int)1e9 + 9;
;
long long powmod(long long a, long long b) {
  if (!b) return 1;
  long long t = powmod(a, b / 2);
  t = (t * t) % MOD;
  if (b & 1) t = (t * a) % MOD;
  return t;
}
map<pair<int, int>, int> isq, pos;
pair<int, int> num[maxn];
set<int, greater<int> > stmax;
set<int> stmin;
int n;
bool isvalid(pair<int, int> a) { return (isq.find(a) != isq.end()); }
bool isstable(pair<int, int> a, int def = INF) {
  if (!isvalid(a)) return false;
  bool f = false;
  for (int t = -1; t < (int)(2); t++)
    f |= (t != def && isvalid(make_pair(a.first + t, a.second - 1)));
  return f;
}
bool istop(pair<int, int> a) {
  if (!isvalid(a)) return false;
  bool f = true;
  for (int t = -1; t < (int)(2); t++)
    f &= (!isvalid(make_pair(a.first + t, a.second + 1)) ||
          isstable(make_pair(a.first + t, a.second + 1), -t));
  return f;
}
void insert(pair<int, int> a) {
  int b = pos[a];
  stmin.insert(b);
  stmax.insert(b);
}
void erase(pair<int, int> a) {
  int b = pos[a];
  stmin.erase(b);
  stmax.erase(b);
}
void recons(pair<int, int> a) {
  if (!isvalid(a)) return;
  if (!istop(a)) erase(a);
}
void check(pair<int, int> a) {
  isq.erase(a);
  for (int t = -1; t < (int)(2); t++)
    if (istop(make_pair(a.first + t, a.second - 1)))
      insert(make_pair(a.first + t, a.second - 1));
  for (int t = -3; t < 4; t++)
    if (t) recons(make_pair(a.first + t, a.second));
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n;
  for (int i = 0; i < (int)(n); i++) {
    cin >> num[i].first >> num[i].second;
    isq[num[i]] = true;
    pos[num[i]] = i;
  }
  for (int i = 0; i < (int)(n); i++) {
    if (istop(num[i])) {
      stmax.insert(i);
      stmin.insert(i);
    }
  }
  vector<int> ans;
  bool turn = false;
  while (!stmin.empty()) {
    if (!turn) {
      int t = *stmax.begin();
      ans.push_back(t);
      stmin.erase(t);
      stmax.erase(t);
      check(num[t]);
    } else {
      int t = *stmin.begin();
      ans.push_back(t);
      stmax.erase(t);
      stmin.erase(t);
      check(num[t]);
    }
    turn ^= 1;
  }
  long long res = 0;
  for (int i = 0; i < (int)(ans.size()); i++) {
    res += (long long)ans[i] * powmod(n, n - i - 1);
    res %= MOD;
  }
  cout << res;
}
