#include <bits/stdc++.h>
using namespace std;
const long long mod = (long long)1e9 + 9;
map<pair<int, int>, int> number;
struct cube {
  int x;
  int y;
  int num;
  cube() { x = y = num; }
  cube(int _x, int _y, int _num) {
    x = _x;
    y = _y;
    num = _num;
  }
};
bool operator<(const cube &left, const cube &right) {
  return left.num < right.num;
}
bool checkgood(int x, int y, set<cube> &v) {
  if (!(v.count(cube(x, y, number[make_pair(x, y)])))) return false;
  for (int dx = -1; dx <= 1; dx++)
    if (v.count(cube(x + dx, y + 1, number[make_pair(x + dx, y + 1)]))) {
      int cntr = 0;
      for (int ndx = -1; ndx <= 1; ndx++)
        if (v.count(cube(x + dx + ndx, y, number[make_pair(x + dx + ndx, y)])))
          cntr++;
      assert(cntr > 0);
      if (cntr == 1) return false;
    }
  return true;
}
void solve(int n) {
  vector<long long> npow(n + 1, 0);
  npow[0] = 1;
  for (int i = 1; i <= n; i++) npow[i] = (npow[i - 1] * n) % mod;
  vector<long long> ans(n);
  set<cube> all, good;
  number.clear();
  int x, y;
  vector<pair<int, int> > temp;
  for (int i = 0; i < n; i++) {
    scanf(" %d %d", &x, &y);
    temp.push_back(make_pair(x, y));
    number[make_pair(x, y)] = i + 1;
    all.insert(cube(x, y, i + 1));
  }
  for (int i = 0; i < n; i++)
    if (checkgood(temp[i].first, temp[i].second, all))
      good.insert(cube(temp[i].first, temp[i].second, i + 1));
  bool Min = false;
  for (int i = n - 1; i >= 0; i--) {
    assert(!good.empty());
    assert((int)good.size() <= (int)all.size());
    cube cur;
    if (Min)
      cur = *good.begin();
    else
      cur = *good.rbegin();
    ans[i] = cur.num;
    good.erase(cur);
    all.erase(cur);
    for (int dx = -1; dx <= 1; dx++)
      if (number.count(make_pair(cur.x + dx, cur.y - 1)))
        if (checkgood(cur.x + dx, cur.y - 1, all))
          good.insert(cube(cur.x + dx, cur.y - 1,
                           number[make_pair(cur.x + dx, cur.y - 1)]));
    for (int dx = -2; dx <= 2; dx++)
      if (number.count(make_pair(cur.x + dx, cur.y)))
        if (!checkgood(cur.x + dx, cur.y, all))
          good.erase(
              cube(cur.x + dx, cur.y, number[make_pair(cur.x + dx, cur.y)]));
    Min ^= true;
  }
  reverse(ans.begin(), ans.end());
  long long answer = 0;
  for (int i = 0; i < n; i++) answer *= n, answer += ans[i] - 1, answer %= mod;
  cout << answer << endl;
}
int main() {
  int n;
  while (cin >> n) solve(n);
}
