#include <bits/stdc++.h>
using namespace std;
const int MaxN = 1e5 + 10;
const int MaxM = 3e5 + 10;
const long long mod = 1e9 + 9;
bool vis[MaxN], able[MaxN];
int xx[MaxN], yy[MaxN], n;
int need[MaxN][3], sup[MaxN][3];
int cntSup[MaxN], cntNeed[MaxN];
priority_queue<int> big;
priority_queue<int, vector<int>, greater<int> > small;
map<pair<int, int>, int> dy;
inline int getnum() {
  int ans = 0;
  char c;
  bool flag = false;
  while ((c = getchar()) == ' ' || c == '\n' || c == '\r')
    ;
  if (c == '-')
    flag = true;
  else
    ans = c - '0';
  while ((c = getchar()) >= '0' && c <= '9') ans = ans * 10 + c - '0';
  return ans * (flag ? -1 : 1);
}
int main() {
  n = getnum();
  for (int i = 1; i <= n; i++) {
    xx[i] = getnum();
    yy[i] = getnum();
    dy[make_pair(xx[i], yy[i])] = i;
  }
  for (int i = 1; i <= n; i++) {
    if (!yy[i]) continue;
    map<pair<int, int>, int>::iterator p;
    p = dy.find(make_pair(xx[i] - 1, yy[i] - 1));
    if (p != dy.end()) {
      cntNeed[i]++;
      need[i][0] = p->second;
      sup[p->second][0] = i;
    }
    p = dy.find(make_pair(xx[i], yy[i] - 1));
    if (p != dy.end()) {
      cntNeed[i]++;
      need[i][1] = p->second;
      sup[p->second][1] = i;
    }
    p = dy.find(make_pair(xx[i] + 1, yy[i] - 1));
    if (p != dy.end()) {
      cntNeed[i]++;
      need[i][2] = p->second;
      sup[p->second][2] = i;
    }
    if (cntNeed[i] == 1)
      for (int j = 0; j < 3; j++)
        if (need[i][j]) cntSup[need[i][j]]++;
  }
  long long ans = 0;
  int st = 1;
  for (int i = 1; i <= n; i++)
    if (!cntSup[i]) {
      big.push(i);
      small.push(i);
      able[i] = true;
    }
  for (int i = 1; i <= n; i++) {
    st ^= 1;
    int now;
    if (!st) {
      while (1) {
        now = big.top();
        big.pop();
        if (!able[now]) continue;
        if (!vis[now]) break;
      }
    } else {
      while (1) {
        now = small.top();
        small.pop();
        if (!able[now]) continue;
        if (!vis[now]) break;
      }
    }
    vis[now] = true;
    ans = (ans * n % mod + now - 1) % mod;
    for (int i = 0; i < 3; i++) {
      int u = sup[now][i];
      if (u && !vis[u]) {
        cntNeed[u]--;
        if (cntNeed[u] == 1) {
          for (int j = 0; j < 3; j++) {
            int v = need[u][j];
            if (v && !vis[v]) {
              cntSup[v]++;
              if (cntSup[v] == 1) able[v] = false;
            }
          }
        }
      }
    }
    if (cntNeed[now] == 1) {
      for (int i = 0; i < 3; i++) {
        int u = need[now][i];
        if (u && !vis[u]) {
          cntSup[u]--;
          if (!cntSup[u]) {
            big.push(u);
            small.push(u);
            able[u] = true;
          }
        }
      }
    }
  }
  cout << ans << endl;
}
