#include <bits/stdc++.h>
using namespace std;
priority_queue<int> large;
priority_queue<int> small;
map<pair<int, int>, bool> freez;
map<pair<int, int>, bool> ex;
map<pair<int, int>, int> val;
pair<int, int> a[100005];
int m;
bool relyOnMaxOne(pair<int, int> s) {
  int cnt = 0;
  pair<int, int> t1, t2, t3;
  t1.first = s.first - 1;
  t1.second = s.second - 1;
  t2.first = s.first;
  t2.second = s.second - 1;
  t3.first = s.first + 1;
  t3.second = s.second - 1;
  if (ex[t1]) cnt++;
  if (ex[t2]) cnt++;
  if (ex[t3]) cnt++;
  if (cnt <= 1) return true;
  return false;
}
bool baz = false;
bool isFree(pair<int, int> s) {
  pair<int, int> t1, t2, t3;
  t1.first = s.first - 1;
  t1.second = s.second + 1;
  t2.first = s.first;
  t2.second = s.second + 1;
  t3.first = s.first + 1;
  t3.second = s.second + 1;
  if ((ex[t1] && relyOnMaxOne(t1))) return false;
  if ((ex[t2] && relyOnMaxOne(t2))) return false;
  if ((ex[t3] && relyOnMaxOne(t3))) return false;
  return true;
}
pair<int, int> curr;
int temp;
vector<int> ret;
void updateFreedom(pair<int, int> s) {
  pair<int, int> t[8];
  t[0].first = s.first - 1;
  t[0].second = s.second - 1;
  t[1].first = s.first;
  t[1].second = s.second - 1;
  t[2].first = s.first + 1;
  t[2].second = s.second - 1;
  t[3].first = s.first - 1;
  t[3].second = s.second;
  t[4].first = s.first;
  t[4].second = s.second;
  t[5].first = s.first + 1;
  t[5].second = s.second;
  t[6].first = s.first - 2;
  t[6].second = s.second;
  t[7].first = s.first + 2;
  t[7].second = s.second;
  for (int i = 0; i <= 7; i++) {
    if (!ex[t[i]]) continue;
    bool al = isFree(t[i]);
    if (al && !freez[t[i]]) {
      freez[t[i]] = true;
      small.push(-val[t[i]]);
      large.push(val[t[i]]);
    } else if (!al && freez[t[i]]) {
      freez[t[i]] = false;
    }
  }
}
int main() {
  scanf("%d", &m);
  for (int i = 0; i < m; i++) {
    scanf("%d %d", &a[i].first, &a[i].second);
    ex[a[i]] = true;
    val[a[i]] = i;
  }
  for (int i = 0; i < m; i++) {
    if (isFree(a[i])) {
      freez[a[i]] = true;
      large.push(val[a[i]]);
      small.push(-val[a[i]]);
    } else
      freez[a[i]] = false;
  }
  for (int i = 1; i <= m; i++) {
    if (i % 2 == 1) {
      bool prvi = true;
      while (prvi || !ex[curr] || !freez[curr]) {
        prvi = false;
        temp = large.top();
        large.pop();
        curr = a[temp];
      }
      ret.push_back(temp);
      ex[curr] = false;
      updateFreedom(curr);
    } else {
      bool prvi = true;
      while (prvi || !ex[curr] || !freez[curr]) {
        prvi = false;
        temp = -small.top();
        small.pop();
        curr = a[temp];
      }
      ret.push_back(temp);
      ex[curr] = false;
      updateFreedom(curr);
    }
  }
  long long retret = 0;
  long long fakt = 1;
  for (int i = ret.size() - 1; i >= 0; i--) {
    retret += fakt * ret[i];
    retret %= 1000000009;
    fakt = (fakt * m) % 1000000009;
  }
  cout << retret << endl;
  return 0;
}
