#include <bits/stdc++.h>
using namespace std;
int maxSize = 100016;
map<pair<int, int>, int> field;
vector<pair<int, int>> invField(maxSize);
class Removables {
 public:
  priority_queue<int> maxCube;
  vector<bool> deleted = vector<bool>(maxSize, false);
  vector<bool> inserted = vector<bool>(maxSize, false);
  priority_queue<int> minCube;
  void add(pair<int, int> a) {
    if (field.find(a) != field.end()) {
      int ind = field[a];
      if (!inserted[ind]) {
        maxCube.push(ind);
        minCube.push(-ind);
      }
      deleted[ind] = false;
      inserted[ind] = true;
    }
  }
  void remove(pair<int, int> a) {
    if (field.find(a) != field.end()) {
      int ind = field[a];
      deleted[ind] = true;
      inserted[ind] = false;
    }
  }
  int popMin() {
    int ind = -minCube.top();
    minCube.pop();
    while (deleted[ind]) {
      ind = -minCube.top();
      minCube.pop();
    }
    deleted[ind] = true;
    return ind;
  }
  int popMax() {
    int ind = maxCube.top();
    maxCube.pop();
    while (deleted[ind]) {
      ind = maxCube.top();
      maxCube.pop();
    }
    deleted[ind] = true;
    return ind;
  }
};
vector<pair<int, int>> belows(pair<int, int> &p) {
  pair<int, int> ll = {p.first - 1, p.second - 1};
  pair<int, int> le = {p.first, p.second - 1};
  pair<int, int> lg = {p.first + 1, p.second - 1};
  return {ll, le, lg};
}
vector<pair<int, int>> aboves(pair<int, int> &p) {
  pair<int, int> ll = {p.first - 1, p.second + 1};
  pair<int, int> le = {p.first, p.second + 1};
  pair<int, int> lg = {p.first + 1, p.second + 1};
  return {ll, le, lg};
}
bool hasBelow(pair<int, int> p) {
  auto l = belows(p);
  bool has = any_of(l.begin(), l.end(), [&](pair<int, int> p) {
    return (field.find(p) != field.end());
  });
  return has;
}
bool hasAbove(pair<int, int> p) {
  int wasV = field[p];
  field.erase(p);
  auto l = aboves(p);
  bool has = any_of(l.begin(), l.end(), [&](pair<int, int> p) {
    return (field.find(p) != field.end() && !hasBelow(p));
  });
  field[p] = wasV;
  return has;
}
int main() {
  ios_base::sync_with_stdio(false);
  int n;
  cin >> n;
  for (int i = 0; i < n; ++i) {
    int x, y;
    cin >> x >> y;
    field[{x, y}] = i;
    invField[i] = {x, y};
  }
  Removables rem;
  for (int i = 0; i < n; ++i) {
    auto p = invField[i];
    if (!hasAbove(p)) {
      rem.add(p);
    }
  }
  vector<int> res;
  for (int i = 0; i < n; ++i) {
    int toRem = (i % 2 == 0) ? rem.popMax() : rem.popMin();
    auto pRem = invField[toRem];
    int wasV = field[pRem];
    field.erase(pRem);
    res.push_back(wasV);
    rem.remove(pRem);
    auto updater = [&](pair<int, int> p) {
      if (field.find(p) != field.end()) {
        if (!hasAbove(p))
          rem.add(p);
        else
          rem.remove(p);
      }
    };
    auto ab = aboves(pRem);
    auto bl = belows(pRem);
    vector<pair<int, int>> nei = {{pRem.first - 2, pRem.second},
                                  {pRem.first - 1, pRem.second},
                                  {pRem.first + 2, pRem.second},
                                  {pRem.first + 1, pRem.second}};
    for_each(ab.begin(), ab.end(), updater);
    for_each(bl.begin(), bl.end(), updater);
    for_each(nei.begin(), nei.end(), updater);
  }
  int64_t modulo = 1000000009;
  int64_t pow = 1;
  int64_t result = 0;
  for (auto it = res.rbegin(); it != res.rend(); ++it) {
    result += pow * (*it);
    result = result % modulo;
    pow *= n;
    pow = pow % modulo;
  }
  cout << result;
  return 0;
}
