#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 9;
const int N = 1e5 + 5;
map<pair<int, int>, int> mp;
int near[N][6];
struct node {
  int x, y;
  long long id;
  bool operator<(const node& a) const { return id < a.id; }
} a[N];
long long p[N];
int vis[N];
set<int> s;
int judge(int id) {
  if (near[id][1])
    if (!near[near[id][1]][5] && !near[near[id][1]][3]) return 0;
  if (near[id][0])
    if (!near[near[id][0]][4] && !near[near[id][0]][3]) return 0;
  if (near[id][2])
    if (!near[near[id][2]][4] && !near[near[id][2]][5]) return 0;
  return 1;
}
void add(int id) {
  if (!id || vis[id]) return;
  if (near[id][1] && !vis[near[id][1]]) {
    if (near[near[id][1]][3] && !vis[near[near[id][1]][3]])
      ;
    else if (near[near[id][1]][5] && !vis[near[near[id][1]][5]])
      ;
    else
      return;
  }
  if (near[id][0] && !vis[near[id][0]]) {
    if (near[near[id][0]][4] && !vis[near[near[id][0]][4]])
      ;
    else if (near[near[id][0]][3] && !vis[near[near[id][0]][3]])
      ;
    else
      return;
  }
  if (near[id][2] && !vis[near[id][2]]) {
    if (near[near[id][2]][4] && !vis[near[near[id][2]][4]])
      ;
    else if (near[near[id][2]][5] && !vis[near[near[id][2]][5]])
      ;
    else
      return;
  }
  s.insert(id);
}
int check(int id) {
  if (near[id][1] && !vis[near[id][1]]) {
    if (!near[near[id][1]][3] && !near[near[id][1]][5]) return 0;
    if (!near[near[id][1]][5])
      if (vis[near[near[id][1]][3]]) return 0;
    if (!near[near[id][1]][3])
      if (vis[near[near[id][1]][5]]) return 0;
    if (near[near[id][1]][3] && vis[near[near[id][1]][3]] &&
        near[near[id][1]][5] && vis[near[near[id][1]][5]])
      return 0;
  }
  if (near[id][0] && !vis[near[id][0]]) {
    if (!near[near[id][0]][4] && !near[near[id][0]][3]) return 0;
    if (!near[near[id][0]][4])
      if (vis[near[near[id][0]][3]]) return 0;
    if (!near[near[id][0]][3])
      if (vis[near[near[id][0]][4]]) return 0;
    if (near[near[id][0]][3] && vis[near[near[id][0]][3]] &&
        near[near[id][0]][4] && vis[near[near[id][0]][4]])
      return 0;
  }
  if (near[id][2] && !vis[near[id][2]]) {
    if (!near[near[id][2]][4] && !near[near[id][2]][5]) return 0;
    if (!near[near[id][2]][4])
      if (vis[near[near[id][2]][5]]) return 0;
    if (!near[near[id][2]][5])
      if (vis[near[near[id][2]][4]]) return 0;
    if (near[near[id][2]][5] && vis[near[near[id][2]][5]] &&
        near[near[id][2]][4] && vis[near[near[id][2]][4]])
      return 0;
  }
  return 1;
}
int main() {
  long long n;
  scanf("%lld", &n);
  long long ret = 1;
  p[0] = 1;
  for (int i = 1; i <= n; i++) {
    ret = ret * n % mod, p[i] = ret;
    scanf("%d%d", &a[i].x, &a[i].y);
    a[i].id = i;
    mp[{a[i].x, a[i].y}] = i;
  }
  for (int i = 1; i <= n; i++) {
    near[i][0] = mp[{a[i].x - 1, a[i].y + 1}];
    near[i][1] = mp[{a[i].x, a[i].y + 1}];
    near[i][2] = mp[{a[i].x + 1, a[i].y + 1}];
    near[i][3] = mp[{a[i].x - 1, a[i].y - 1}];
    near[i][4] = mp[{a[i].x, a[i].y - 1}];
    near[i][5] = mp[{a[i].x + 1, a[i].y - 1}];
  }
  for (int i = 1; i <= n; i++)
    if (judge(i)) s.insert(i);
  int f = 0, r = n - 1;
  set<int>::iterator it;
  long long ans = 0;
  while (!s.empty()) {
    if (!f) {
      it = s.end();
      it--;
      while (!check(*it)) s.erase(it--);
      int pos = *it;
      ans = (ans + (a[pos].id - 1ll) * p[r]) % mod;
      vis[a[pos].id] = 1;
      add(near[pos][4]), add(near[pos][3]), add(near[pos][5]);
      s.erase(it);
    } else {
      it = s.begin();
      while (!check(*it)) s.erase(it++);
      int pos = *it;
      ans = (ans + (a[pos].id - 1ll) * p[r]) % mod;
      vis[a[pos].id] = 1;
      add(near[pos][4]), add(near[pos][3]), add(near[pos][5]);
      s.erase(it);
    }
    r--, f ^= 1;
  }
  printf("%lld\n", ans);
  return 0;
}
