#include <bits/stdc++.h>
using namespace std;
template <typename T>
struct Z_p {
  using Type = typename decay<decltype(T::value)>::type;
  static vector<Type> MOD_INV;
  constexpr Z_p() : value() {}
  template <typename U>
  Z_p(const U &x) {
    value = normalize(x);
  }
  template <typename U>
  static Type normalize(const U &x) {
    Type v;
    if (-mod() <= x && x < mod())
      v = static_cast<Type>(x);
    else
      v = static_cast<Type>(x % mod());
    if (v < 0) v += mod();
    return v;
  }
  const Type &operator()() const { return value; }
  template <typename U>
  explicit operator U() const {
    return static_cast<U>(value);
  }
  constexpr static Type mod() { return T::value; }
  Z_p &operator+=(const Z_p &otr) {
    if ((value += otr.value) >= mod()) value -= mod();
    return *this;
  }
  Z_p &operator-=(const Z_p &otr) {
    if ((value -= otr.value) < 0) value += mod();
    return *this;
  }
  template <typename U>
  Z_p &operator+=(const U &otr) {
    return *this += Z_p(otr);
  }
  template <typename U>
  Z_p &operator-=(const U &otr) {
    return *this -= Z_p(otr);
  }
  Z_p &operator++() { return *this += 1; }
  Z_p &operator--() { return *this -= 1; }
  Z_p operator++(int) {
    Z_p result(*this);
    *this += 1;
    return result;
  }
  Z_p operator--(int) {
    Z_p result(*this);
    *this -= 1;
    return result;
  }
  Z_p operator-() const { return Z_p(-value); }
  template <typename U = T>
  typename enable_if<is_same<typename Z_p<U>::Type, int>::value, Z_p>::type &
  operator*=(const Z_p &rhs) {
    value = normalize(static_cast<int64_t>(value) *
                      static_cast<int64_t>(rhs.value));
    return *this;
  }
  template <typename U = T>
  typename enable_if<is_same<typename Z_p<U>::Type, int64_t>::value, Z_p>::type
      &
      operator*=(const Z_p &rhs) {
    int64_t q = static_cast<int64_t>(static_cast<long double>(value) *
                                     rhs.value / mod());
    value = normalize(value * rhs.value - q * mod());
    return *this;
  }
  template <typename U = T>
  typename enable_if<!is_integral<typename Z_p<U>::Type>::value, Z_p>::type &
  operator*=(const Z_p &rhs) {
    value = normalize(value * rhs.value);
    return *this;
  }
  template <typename U>
  Z_p &operator^=(U e) {
    if (e < 0) *this = 1 / *this, e = -e;
    Z_p res = 1;
    for (; e; *this *= *this, e >>= 1)
      if (e & 1) res *= *this;
    return *this = res;
  }
  template <typename U>
  Z_p operator^(U e) const {
    return Z_p(*this) ^= e;
  }
  Z_p &operator/=(const Z_p &otr) {
    Type a = otr.value, m = mod(), u = 0, v = 1;
    if (a < (int)MOD_INV.size()) return *this *= MOD_INV[a];
    while (a) {
      Type t = m / a;
      m -= t * a;
      swap(a, m);
      u -= t * v;
      swap(u, v);
    }
    assert(m == 1);
    return *this *= u;
  }
  template <typename U>
  friend const Z_p<U> &abs(const Z_p<U> &v) {
    return v;
  }
  Type value;
};
template <typename T>
bool operator==(const Z_p<T> &lhs, const Z_p<T> &rhs) {
  return lhs.value == rhs.value;
}
template <typename T, typename U,
          typename enable_if<is_integral<U>::value>::type * = nullptr>
bool operator==(const Z_p<T> &lhs, U rhs) {
  return lhs == Z_p<T>(rhs);
}
template <typename T, typename U,
          typename enable_if<is_integral<U>::value>::type * = nullptr>
bool operator==(U lhs, const Z_p<T> &rhs) {
  return Z_p<T>(lhs) == rhs;
}
template <typename T>
bool operator!=(const Z_p<T> &lhs, const Z_p<T> &rhs) {
  return !(lhs == rhs);
}
template <typename T, typename U,
          typename enable_if<is_integral<U>::value>::type * = nullptr>
bool operator!=(const Z_p<T> &lhs, U rhs) {
  return !(lhs == rhs);
}
template <typename T, typename U,
          typename enable_if<is_integral<U>::value>::type * = nullptr>
bool operator!=(U lhs, const Z_p<T> &rhs) {
  return !(lhs == rhs);
}
template <typename T>
bool operator<(const Z_p<T> &lhs, const Z_p<T> &rhs) {
  return lhs.value < rhs.value;
}
template <typename T>
bool operator>(const Z_p<T> &lhs, const Z_p<T> &rhs) {
  return lhs.value > rhs.value;
}
template <typename T>
bool operator<=(const Z_p<T> &lhs, const Z_p<T> &rhs) {
  return lhs.value <= rhs.value;
}
template <typename T>
bool operator>=(const Z_p<T> &lhs, const Z_p<T> &rhs) {
  return lhs.value >= rhs.value;
}
template <typename T>
Z_p<T> operator+(const Z_p<T> &lhs, const Z_p<T> &rhs) {
  return Z_p<T>(lhs) += rhs;
}
template <typename T, typename U,
          typename enable_if<is_integral<U>::value>::type * = nullptr>
Z_p<T> operator+(const Z_p<T> &lhs, U rhs) {
  return Z_p<T>(lhs) += rhs;
}
template <typename T, typename U,
          typename enable_if<is_integral<U>::value>::type * = nullptr>
Z_p<T> operator+(U lhs, const Z_p<T> &rhs) {
  return Z_p<T>(lhs) += rhs;
}
template <typename T>
Z_p<T> operator-(const Z_p<T> &lhs, const Z_p<T> &rhs) {
  return Z_p<T>(lhs) -= rhs;
}
template <typename T, typename U,
          typename enable_if<is_integral<U>::value>::type * = nullptr>
Z_p<T> operator-(const Z_p<T> &lhs, U rhs) {
  return Z_p<T>(lhs) -= rhs;
}
template <typename T, typename U,
          typename enable_if<is_integral<U>::value>::type * = nullptr>
Z_p<T> operator-(U lhs, const Z_p<T> &rhs) {
  return Z_p<T>(lhs) -= rhs;
}
template <typename T>
Z_p<T> operator*(const Z_p<T> &lhs, const Z_p<T> &rhs) {
  return Z_p<T>(lhs) *= rhs;
}
template <typename T, typename U,
          typename enable_if<is_integral<U>::value>::type * = nullptr>
Z_p<T> operator*(const Z_p<T> &lhs, U rhs) {
  return Z_p<T>(lhs) *= rhs;
}
template <typename T, typename U,
          typename enable_if<is_integral<U>::value>::type * = nullptr>
Z_p<T> operator*(U lhs, const Z_p<T> &rhs) {
  return Z_p<T>(lhs) *= rhs;
}
template <typename T>
Z_p<T> operator/(const Z_p<T> &lhs, const Z_p<T> &rhs) {
  return Z_p<T>(lhs) /= rhs;
}
template <typename T, typename U,
          typename enable_if<is_integral<U>::value>::type * = nullptr>
Z_p<T> operator/(const Z_p<T> &lhs, U rhs) {
  return Z_p<T>(lhs) /= rhs;
}
template <typename T, typename U,
          typename enable_if<is_integral<U>::value>::type * = nullptr>
Z_p<T> operator/(U lhs, const Z_p<T> &rhs) {
  return Z_p<T>(lhs) /= rhs;
}
template <typename T>
istream &operator>>(istream &in, Z_p<T> &number) {
  typename common_type<typename Z_p<T>::Type, int64_t>::type x;
  in >> x;
  number.value = Z_p<T>::normalize(x);
  return in;
}
template <typename T>
ostream &operator<<(ostream &out, const Z_p<T> &number) {
  return out << number();
}
constexpr int mod = 1e9 + 9;
using Zp = Z_p<integral_constant<decay<decltype(mod)>::type, mod>>;
template <typename T>
vector<typename Z_p<T>::Type> Z_p<T>::MOD_INV;
template <typename T = integral_constant<decay<decltype(mod)>::type, mod>>
void precalc_inverse(int SZ) {
  auto &inv = Z_p<T>::MOD_INV;
  if (inv.empty()) inv.assign(2, 1);
  for (; inv.size() <= SZ;)
    inv.push_back(
        (mod - 1LL * mod / (int)inv.size() * inv[mod % (int)inv.size()]) % mod);
}
template <typename T>
vector<T> precalc_power(T base, int SZ) {
  vector<T> res(SZ + 1, 1);
  for (auto i = 1; i <= SZ; ++i) res[i] = res[i - 1] * base;
  return res;
}
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin.exceptions(ios::badbit | ios::failbit);
  int n;
  cin >> n;
  vector<array<int, 2>> a(n);
  map<int, map<int, int>> occur;
  for (auto i = 0; i < n; ++i) {
    cin >> a[i][0] >> a[i][1];
    occur[a[i][1]].insert({a[i][0], i});
  }
  auto cnt = [&](int i) -> int {
    auto [x, y] = a[i];
    auto &lower = occur[y - 1];
    int res = 0;
    for (auto it = lower.lower_bound(x - 1);
         it != lower.end() && it->first <= x + 1; ++it) {
      ++res;
    }
    42;
    return res;
  };
  auto removable = [&](int i) -> bool {
    auto [x, y] = a[i];
    if (!occur.count(y + 1)) {
      return true;
    }
    auto &upper = occur[y + 1];
    for (auto it = upper.lower_bound(x - 1);
         it != upper.end() && it->first <= x + 1; ++it) {
      if (int x = cnt(it->second); assert(x), x == 1) {
        return false;
      }
    }
    return true;
  };
  set<int> s;
  for (auto i = 0; i < n; ++i) {
    if (removable(i)) {
      42;
      s.insert(i);
    }
  }
  Zp res = 0;
  auto pow = precalc_power(Zp(n), n);
  for (auto rep = 0; rep < n; ++rep) {
    assert(!s.empty());
    int i;
    if (~rep & 1) {
      i = *s.rbegin(), s.erase(prev(s.end()));
    } else {
      i = *s.begin(), s.erase(s.begin());
    }
    occur[a[i][1]].erase(a[i][0]);
    42;
    res += pow[n - 1 - rep] * i;
    auto [x, y] = a[i];
    auto &lower = occur[y - 1];
    for (auto it = lower.lower_bound(x - 1);
         it != lower.end() && it->first <= x + 1; ++it) {
      if (removable(it->second)) {
        s.insert(it->second);
      } else {
        s.erase(it->second);
      }
    }
    auto &same = occur[y];
    for (auto it = same.lower_bound(x - 2);
         it != same.end() && it->first <= x + 2; ++it) {
      if (it->second == i) {
        continue;
      }
      if (removable(it->second)) {
        s.insert(it->second);
      } else {
        s.erase(it->second);
      }
    }
    42;
  }
  cout << res << "\n";
  return 0;
}
