#include <bits/stdc++.h>
using namespace std;
const long long int mod = 1e9 + 9;
int add(long long int x, long long int y) { return (x + y) % mod; }
int mul(long long int x, long long int y) { return (x * y) % mod; }
int n;
pair<int, int> a[112345];
map<pair<int, int>, int> b;
map<pair<int, int>, int>::iterator bi;
map<pair<int, int>, int> m;
map<pair<int, int>, int>::iterator mi;
set<int> s;
set<int>::iterator si;
bool exist(pair<int, int> p) { return m.count(p); }
int countUnder(pair<int, int> p) {
  int ret = 0;
  for (int i = -1; i <= +1; i++)
    ret += exist(make_pair(p.first + i, p.second - 1));
  return ret;
}
int giveNumber(pair<int, int> p) {
  bi = b.find(p);
  if (bi == b.end()) return -1;
  return bi->second;
}
int under(pair<int, int> p) {
  map<pair<int, int>, int>::iterator mi = m.find(p);
  if (mi == m.end()) return 1e9;
  return mi->second;
}
bool isDestroyable(pair<int, int> p) {
  for (int i = -1; i <= +1; i++)
    if (under(make_pair(p.first + i, p.second + 1)) < 2) return false;
  return true;
}
void del(pair<int, int> p) {
  m.erase(m.find(p));
  for (int i = -1; i <= +1; i++) {
    mi = m.find(make_pair(p.first + i, p.second + 1));
    if (mi != m.end()) mi->second--;
  }
  for (int i = -1; i <= +1; i++) {
    pair<int, int> q = make_pair(p.first + i, p.second - 1);
    mi = m.find(q);
    if (mi != m.end() && isDestroyable(q)) {
      int num = giveNumber(q);
      s.insert(num);
    }
  }
  for (int i = -2; i <= +2; i++) {
    if (i == 0) continue;
    pair<int, int> q = make_pair(p.first + i, p.second);
    mi = m.find(q);
    if (mi != m.end() && isDestroyable(q) == false) {
      int num = giveNumber(q);
      s.erase(num);
    }
  }
}
int main() {
  cin >> n;
  for (int i = 0; i < n; i++) {
    int x, y;
    cin >> x >> y;
    a[i].first = x, a[i].second = y;
    b[a[i]] = i;
    m[a[i]] = 0;
  }
  for (int i = 0; i < n; i++) {
    m[a[i]] = countUnder(a[i]);
  }
  for (int i = 0; i < n; i++)
    if (isDestroyable(a[i])) s.insert(i);
  int ans[112345] = {};
  for (int i = 0; i < n; i++) {
    if (i % 2 == 0) {
      int num = *s.rbegin();
      ans[i] = num;
      s.erase(--s.end());
      pair<int, int> p = a[num];
      del(p);
    } else {
      int num = *s.begin();
      ans[i] = num;
      s.erase(s.begin());
      pair<int, int> p = a[num];
      del(p);
    }
  }
  int z = 1, sol = 0;
  for (int i = n - 1; i >= 0; i--) {
    sol = add(sol, mul(ans[i], z));
    z = mul(z, n);
  }
  cout << sol << "\n";
  return 0;
}
