#include <bits/stdc++.h>
using namespace std;
template <typename T1, typename T2>
istream &operator>>(istream &in, pair<T1, T2> &a) {
  in >> a.first >> a.second;
  return in;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &out, pair<T1, T2> a) {
  out << a.first << " " << a.second;
  return out;
}
template <typename T>
pair<T, T> operator+=(pair<T, T> &a, pair<T, T> b) {
  a.first += b.first;
  a.second += b.second;
  return a;
}
template <typename T>
pair<T, T> operator-=(pair<T, T> &a, pair<T, T> b) {
  a.first -= b.first;
  a.second -= b.second;
  return a;
}
template <typename T>
pair<T, T> operator+(pair<T, T> a, pair<T, T> b) {
  a.first += b.first;
  a.second += b.second;
  return a;
}
template <typename T>
pair<T, T> operator-(pair<T, T> a, pair<T, T> b) {
  a.first -= b.first;
  a.second -= b.second;
  return a;
}
template <typename T, typename T1>
T amax(T &a, T1 b) {
  if (b > a) a = b;
  return a;
}
template <typename T, typename T1>
T amin(T &a, T1 b) {
  if (b < a) a = b;
  return a;
}
const long long N = 1e5 + 5;
map<long long, long long> ids[N];
pair<long long, long long> x[N];
long long supports[N];
set<long long> rem;
vector<long long> ans;
bool check(long long id) {
  long long f = 1;
  long long a = x[id].first, b = x[id].second;
  for (long long i = -1; i < 2; i++) {
    if (ids[b + 1].count(a + i)) {
      if (supports[ids[b + 1][a + i]] == 1) f = 0;
    }
  }
  return f;
}
void solve() {
  long long n;
  cin >> n;
  for (long long i = 0; i < n; i++) {
    cin >> x[i];
    ids[x[i].second][x[i].first] = i;
  }
  for (long long i = 0; i < n; i++) {
    long long a = x[i].first, b = x[i].second;
    for (long long i = -1; i < 2; i++) {
      if (ids[b + 1].count(a + i)) {
        supports[ids[b + 1][a + i]]++;
      }
    }
  }
  for (long long i = 0; i < n; i++) {
    if (check(i)) rem.insert(i);
  }
  for (long long i = 0; i < n; i++) {
    long long rid;
    if (i % 2 == 0) {
      rid = *rem.rbegin();
    } else {
      rid = *rem.begin();
    }
    ans.push_back(rid);
    rem.erase(rid);
    long long a = x[rid].first, b = x[rid].second;
    ids[b].erase(a);
    for (long long i = -1; i < 2; i++) {
      if (ids[b + 1].count(a + i)) {
        supports[ids[b + 1][a + i]]--;
      }
    }
    if (b)
      for (long long i = -1; i < 2; i++) {
        if (ids[b - 1].count(a + i)) {
          long long k = ids[b - 1][a + i];
          if (check(k)) rem.insert(k);
        }
      }
    for (long long i = -2; i < 3; i++) {
      if (i == 0) continue;
      if (ids[b].count(a + i)) {
        long long k = ids[b][a + i];
        if (!check(k)) rem.erase(k);
      }
    }
  }
  reverse((ans).begin(), (ans).end());
  long long m = 1;
  long long rr = 0;
  for (long long x : ans) {
    rr += x * m % 1000000009;
    rr %= 1000000009;
    m *= n;
    m %= 1000000009;
  }
  cout << rr;
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long t = 1;
  while (t--) solve();
  return 0;
}
