#include <bits/stdc++.h>
using namespace std;
const long long MAXN = 1e5 + 10, md = 1e9 + 9;
set<long long> mn, mx;
map<pair<long long, long long>, long long> mp;
long long kx[] = {-2, -1, 1, 2, -1, 0, 1};
long long ky[] = {0, 0, 0, 0, -1, -1, -1};
bool check(long long x, long long y) {
  if (!mp.count({x, y})) return true;
  if (!y) return true;
  return (mp.count({x - 1, y - 1}) + mp.count({x, y - 1}) +
              mp.count({x + 1, y - 1}) >
          1);
}
void upd(long long x, long long y) {
  if (!mp.count({x, y})) return;
  long long now = mp[{x, y}];
  if (check(x - 1, y + 1) && check(x, y + 1) && check(x + 1, y + 1)) {
    mn.insert(now);
    mx.insert(-now);
  } else {
    mn.erase(now);
    mx.erase(-now);
  }
}
pair<long long, long long> node[MAXN];
int32_t main() {
  long long n, a1, a2;
  cin >> n;
  for (long long i = 0; i < n; ++i) {
    cin >> a1 >> a2;
    node[i] = {a1, a2};
    mp[{a1, a2}] = i;
  }
  vector<long long> ans;
  for (long long i = 0; i < n; ++i) upd(node[i].first, node[i].second);
  for (long long i = 0; i < n; ++i) {
    long long now = ((i % 2) == 0 ? -(*mx.begin()) : *mn.begin());
    ans.push_back(now);
    mx.erase(-now);
    mn.erase(now);
    mp.erase(node[now]);
    for (long long i = 0; i < 7; ++i)
      upd(node[now].first + kx[i], node[now].second + ky[i]);
  }
  long long res = 0;
  for (auto i : ans) res = (res * n + i) % md;
  cout << res;
  return 0;
}
