#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 9;
const int N = 100005;
pair<int, int> arr[N];
map<pair<int, int>, int> id;
set<int> up[N];
int upsz[N];
set<int> down[N];
int downsz[N];
bool take[N];
void add(int u, int d) {
  down[u].insert(d);
  up[d].insert(u);
  ++downsz[u];
  ++upsz[d];
}
set<int> valid;
bool val[N];
bool check(int id) {
  set<int>::iterator i = up[id].begin();
  while (i != up[id].end()) {
    if (!take[*i] && downsz[*i] == 1) return 0;
    ++i;
  }
  return 1;
}
void checkdown(int idx) {
  set<int>::iterator i = down[idx].begin();
  while (i != down[idx].end()) {
    if (!take[*i] && check(*i))
      valid.insert(*i);
    else if (!take[*i]) {
      valid.erase(*i);
    }
    ++i;
  }
}
void del(int idx) {
  set<int>::iterator i = up[idx].begin();
  while (i != up[idx].end()) {
    if (!take[*i]) {
      --downsz[*i];
      checkdown(*i);
    }
    ++i;
  }
  i = down[idx].begin();
  while (i != down[idx].end()) {
    --upsz[*i];
    if (!take[*i] && check(*i))
      valid.insert(*i);
    else if (!take[*i])
      valid.erase(*i);
    ++i;
  }
  valid.erase(idx);
}
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    scanf("%d%d", &arr[i - 1].first, &arr[i - 1].second);
    id[arr[i - 1]] = i;
    swap(arr[i - 1].first, arr[i - 1].second);
  }
  sort(arr, arr + n);
  for (int i = 0; i < n; ++i) {
    if (arr[i].first) {
      pair<int, int> c = arr[i];
      swap(c.first, c.second);
      int v = id[c];
      --c.first;
      --c.second;
      for (int i = 0; i < 3; ++c.first, ++i) {
        int w = id[c];
        if (w > 0) add(v, w);
      }
    }
  }
  for (int i = 0; i < n; ++i) {
    pair<int, int> c = arr[i];
    swap(c.first, c.second);
    int v = id[c];
    if (check(v)) {
      valid.insert(v);
    }
  }
  long long ans = 0;
  for (int i = 0; i < n; ++i) {
    set<int>::iterator z = valid.end();
    --z;
    take[*z] = 1;
    ans *= (1ll * n);
    ans += ((*z) - 1);
    ans %= mod;
    del(*z);
    ++i;
    if (i == n) break;
    z = valid.begin();
    take[*z] = 1;
    ans *= n;
    ans += ((*z) - 1);
    ans %= mod;
    del(*z);
  }
  printf("%lld", ans % mod);
}
