#include <bits/stdc++.h>
using namespace std;
int n;
long long xx[100001];
long long yy[100001];
struct Point2DbyXY {
  long long x, y;
  Point2DbyXY(){};
  Point2DbyXY(long long a, long long b) { x = a, y = b; };
  bool operator<(const Point2DbyXY& P) const {
    if (x < P.x) return true;
    if (x > P.x) return false;
    return (y < P.y);
  };
};
stack<long long> sol;
map<Point2DbyXY, int> markm;
struct edge1 {
  int d;
  edge1(){};
  edge1(int dd) { d = dd; };
  bool operator<(const edge1& X) const { return d > X.d; }
};
struct edge2 {
  int d;
  edge2(){};
  edge2(int dd) { d = dd; };
  bool operator<(const edge2& X) const { return d < X.d; }
};
priority_queue<edge1> menores;
priority_queue<edge2> mayores;
int firstdigit[100001];
int laided[100001];
int HowManyBelow(int p) {
  int v, cnt = 0;
  v = markm[Point2DbyXY(xx[p], yy[p] - 1)];
  if (v && !laided[v]) cnt++;
  v = markm[Point2DbyXY(xx[p] - 1, yy[p] - 1)];
  if (v && !laided[v]) cnt++;
  v = markm[Point2DbyXY(xx[p] + 1, yy[p] - 1)];
  if (v && !laided[v]) cnt++;
  return cnt;
}
int HowManyBelowCent(int p) {
  int v = markm[Point2DbyXY(xx[p], yy[p] - 1)];
  if (v && !laided[v]) return v;
  return 0;
}
int HowManyBelowLeft(int p) {
  int v = markm[Point2DbyXY(xx[p] - 1, yy[p] - 1)];
  if (v && !laided[v]) return v;
  return 0;
}
int HowManyBelowRigh(int p) {
  int v = markm[Point2DbyXY(xx[p] + 1, yy[p] - 1)];
  if (v && !laided[v]) return v;
  return 0;
}
int HowManyAboveCent(int p) {
  int v = markm[Point2DbyXY(xx[p], yy[p] + 1)];
  if (v && !laided[v]) return v;
  return 0;
}
int HowManyAboveLeft(int p) {
  int v = markm[Point2DbyXY(xx[p] - 1, yy[p] + 1)];
  if (v && !laided[v]) return v;
  return 0;
}
int HowManyAboveRigh(int p) {
  int v = markm[Point2DbyXY(xx[p] + 1, yy[p] + 1)];
  if (v && !laided[v]) return v;
  return 0;
}
bool Check(int p) {
  int flag = true;
  if (0 == p) return false;
  int mid = HowManyAboveCent(p);
  if (mid && flag) {
    if (1 == HowManyBelow(markm[Point2DbyXY(xx[p], yy[p] + 1)])) flag = false;
  }
  int lft = HowManyAboveLeft(p);
  if (lft && flag) {
    if (1 == HowManyBelow(markm[Point2DbyXY(xx[p] - 1, yy[p] + 1)]))
      flag = false;
  }
  int rgh = HowManyAboveRigh(p);
  if (rgh && flag) {
    if (1 == HowManyBelow(markm[Point2DbyXY(xx[p] + 1, yy[p] + 1)]))
      flag = false;
  }
  if (flag) {
    menores.push(edge1(p));
    mayores.push(edge2(p));
    return true;
  }
  return false;
}
void PlayMax() {
  int v = 0;
  laided[0] = 1;
  while (1 == laided[v] || !Check(v)) {
    v = mayores.top().d;
    mayores.pop();
  }
  laided[v] = 1;
  sol.push(v - 1);
  int mid = HowManyBelowCent(v);
  if (mid) Check(mid);
  int lft = HowManyBelowLeft(v);
  if (lft) Check(lft);
  int rgh = HowManyBelowRigh(v);
  if (rgh) Check(rgh);
}
void PlayMin() {
  int v = 0;
  laided[0] = 1;
  while (1 == laided[v] || !Check(v)) {
    v = menores.top().d;
    menores.pop();
  }
  laided[v] = 1;
  sol.push(v - 1);
  int mid = HowManyBelowCent(v);
  if (mid) Check(mid);
  int lft = HowManyBelowLeft(v);
  if (lft) Check(lft);
  int rgh = HowManyBelowRigh(v);
  if (rgh) Check(rgh);
}
int main() {
  scanf("%d", &n);
  for (int p = (1); p <= (n); p += (1)) {
    laided[p] = 0;
    scanf("%d%d", &xx[p], &yy[p]);
    markm[Point2DbyXY(xx[p], yy[p])] = p;
  }
  for (int p = (1); p <= (n); p += (1)) Check(p);
  for (int p = (1); p <= (n); p += (1)) {
    if (1 == p % 2)
      PlayMax();
    else
      PlayMin();
  }
  long long SOL = 0;
  long long bpower = 1;
  long long M = 1000000009;
  while (!sol.empty()) {
    SOL += bpower * sol.top();
    bpower *= n;
    bpower %= M;
    sol.pop();
    SOL %= M;
  }
  cout << SOL << endl;
}
