#include <bits/stdc++.h>
using namespace std;
const long long mod = 1000000009ll;
const long long _3 = 333333336ll;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
long long fpow(long long a, long long b) {
  long long ret = 1;
  while (b) {
    if (b % 2 == 1) {
      ret *= a;
      ret %= mod;
    }
    a = a * a;
    a %= mod;
    b /= 2;
  }
  return ret;
}
struct s {
  long long val;
  int x, y;
  bool operator<(const s &I) const { return val < I.val; }
};
s num[100009];
set<s> sets;
map<pair<int, int>, int> m;
int n;
int vis[100009];
int rmd[100009];
int count_suppoter(int x, int y) {
  int cc = 0;
  for (int i = -1; i <= 1; i++) {
    if (m[make_pair(x + i, y - 1)] != 0 &&
        rmd[num[m[make_pair(x + i, y - 1)]].val] == 0)
      cc++;
  }
  return cc;
}
bool ok_to_rm(s a) {
  int x = a.x;
  int y = a.y;
  for (int i = -1; i <= 1; i++) {
    if (m[make_pair(x + i, y + 1)] != 0 &&
        rmd[num[m[make_pair(x + i, y + 1)]].val] == 0 &&
        count_suppoter(x + i, y + 1) == 1)
      return false;
  }
  return true;
}
void add(s a) {
  if (a.y == 0) return;
  int x = a.x, y = a.y;
  for (int i = -1; i <= 1; i++) {
    if (m[make_pair(x + i, y - 1)] == 0 ||
        vis[num[m[make_pair(x + i, y - 1)]].val] == 1)
      continue;
    if (ok_to_rm(num[m[make_pair(x + i, y - 1)]])) {
      vis[num[m[make_pair(x + i, y - 1)]].val] = 1;
      sets.insert(num[m[make_pair(x + i, y - 1)]]);
    }
  }
}
void del(s a) {
  int x = a.x, y = a.y;
  for (int i = -2; i <= 2; i++) {
    if (i == 0) continue;
    int hd = m[make_pair(x + i, y)];
    if (hd == 0) continue;
    if (rmd[num[hd].val] == 0 && !ok_to_rm(num[hd]) && vis[num[hd].val]) {
      vis[num[hd].val] = 0;
      sets.erase(num[hd]);
    }
  }
}
int MAIN() {
  scanf("%d", &n);
  memset((vis), (0), sizeof(vis));
  memset((rmd), (0), sizeof(rmd));
  for (int i = 1; i <= n; i++) {
    scanf("%d%d", &num[i].x, &num[i].y);
    num[i].val = i - 1;
    m[make_pair(num[i].x, num[i].y)] = i;
  }
  for (int i = 1; i <= n; i++) {
    if (ok_to_rm(num[i])) {
      sets.insert(num[i]);
      vis[num[i].val] = 1;
    }
  }
  long long ans = 0;
  for (int i = 0; i < n; i++) {
    s trm;
    if (i % 2 != 0) {
      trm = *(sets.begin());
    } else {
      trm = *(sets.rbegin());
    }
    ans = ans * n % mod + trm.val;
    ans %= mod;
    sets.erase(trm);
    rmd[trm.val] = 1;
    add(trm);
    del(trm);
  }
  printf("%lld\n", ans);
  return 0;
}
int main() {
  MAIN();
  return 0;
}
