#include <bits/stdc++.h>
using namespace std;
set<int> q;
int m;
pair<int, int> dat[111111];
map<pair<int, int>, int> mp;
const long long mof = 1e9 + 9;
inline long long pow_mod(long long a, long long k, long long mo) {
  long long ans = 1;
  while (k) {
    if (k % 2) ans = ans * a % mo;
    a = a * a % mo;
    k >>= 1;
  }
  return ans % mo;
}
long long ans;
bool inque[111111];
pair<int, int> lef(pair<int, int> x) {
  pair<int, int> y = x;
  y.first--;
  return y;
}
pair<int, int> righ(pair<int, int> x) {
  pair<int, int> y = x;
  y.first++;
  return y;
}
pair<int, int> dwn(pair<int, int> x) {
  pair<int, int> y = x;
  y.second--;
  return y;
}
pair<int, int> up(pair<int, int> x) {
  pair<int, int> y = x;
  y.second++;
  return y;
}
bool ok(pair<int, int> x) {
  pair<int, int> y = up(x);
  if (!mp.count(lef(y)) && !mp.count(y) && !mp.count(righ(y))) return true;
  if (mp.count(lef(y))) {
    pair<int, int> ty = dwn(lef(y));
    if (!mp.count(ty) && !mp.count(lef(ty))) return false;
  }
  if (mp.count(y)) {
    pair<int, int> ty = dwn(y);
    if (!mp.count(lef(ty)) && !mp.count(righ(ty))) return false;
  }
  if (mp.count(righ(y))) {
    pair<int, int> ty = dwn(righ(y));
    if (!mp.count(ty) && !mp.count(righ(ty))) return false;
  }
  return true;
}
int main() {
  cin >> m;
  for (int i = 0; i < m; ++i)
    cin >> dat[i].first >> dat[i].second, mp[dat[i]] = i;
  for (int i = 0; i < m; ++i)
    if (ok(dat[i])) q.insert(i), inque[i] = true;
  long long bas = m - 1;
  int rd = 0;
  while (!q.empty()) {
    rd++;
    long long t;
    if (rd % 2 == 0)
      t = *q.begin();
    else
      t = *q.rbegin();
    q.erase(t);
    mp.erase(dat[t]);
    pair<int, int> xx = lef(dat[t]);
    if (mp.count(lef(xx)) && inque[mp[lef(xx)]] && !ok(lef(xx))) {
      inque[mp[lef(xx)]] = false;
      q.erase(mp[lef(xx)]);
    }
    if (mp.count(xx) && inque[mp[xx]] && !ok(xx)) {
      inque[mp[xx]] = false;
      q.erase(mp[xx]);
    }
    xx = righ(dat[t]);
    if (mp.count(righ(xx)) && inque[mp[righ(xx)]] && !ok(righ(xx))) {
      inque[mp[righ(xx)]] = false;
      q.erase(mp[righ(xx)]);
    }
    if (mp.count(xx) && inque[mp[xx]] && !ok(xx)) {
      inque[mp[xx]] = false;
      q.erase(mp[xx]);
    }
    ans = (ans + t * pow_mod(m, bas, mof) % mof) % mof;
    bas--;
    pair<int, int> tt = dat[t];
    tt.second--;
    tt.first--;
    for (int i = 0; i < 3; ++i) {
      if (mp.count(tt) && !inque[mp[tt]] && ok(tt)) {
        inque[mp[tt]] = true;
        q.insert(mp[tt]);
      }
      tt.first++;
    }
  }
  cout << ans << endl;
}
