#include <bits/stdc++.h>   #pragma GCC optimize( O3 )   using namespace std;   int add(int a, int b) {     long long x = a + b;     if (x >= 1000000009) x -= 1000000009;     if (x < 0) x += 1000000009;     return x;   }   long long mul(long long a, long long b) { return (a * b) % 1000000009; }   long long pw(long long a, long long b) {     long long ans = 1;     while (b) {       if (b & 1) ans = (ans * a) % 1000000009;       a = (a * a) % 1000000009;       b >>= 1;     }     return ans;   }   mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());   long long rand_seed() {     long long a = rng();     return a;   }   int n;   map<int, pair<int, int> > pos;   map<pair<int, int>, int> id;   vector<set<int> > p, ch;   bool canrem(int i) {     int ok = 1;     for (auto j : p[i]) ok &= (ch[j].size() > 1);     return ok;   }   void rem(int i) {     for (auto j : p[i]) ch[j].erase(i);     for (auto j : ch[i]) p[j].erase(i);   }   int main() {     ios_base::sync_with_stdio(false);     cin.tie(NULL);     cin >> n;     p.resize(n);     ch.resize(n);     for (int x, y, i = 0; i < n; i++) {       cin >> y >> x;       pos[i] = {x, y};       id[{x, y}] = i;     }     for (int i = 0; i < n; i++) {       int x = pos[i].first, y = pos[i].second;       for (int z = -1; z < 2; z++) {         if (id.count({x + 1, y + z})) p[i].insert(id[{x + 1, y + z}]);         if (id.count({x - 1, y + z})) ch[i].insert(id[{x - 1, y + z}]);       }     }     set<int> can;     for (int i = 0; i < n; i++) {       int x = pos[i].first, y = pos[i].second;       if (canrem(i)) can.insert(i);     }     long long ans = 0;     for (int i = 0; i < n; i++) {       int j;       if (i % 2 == 0)         j = *can.rbegin();       else         j = *can.begin();       ans = mul(ans, n);       ans = add(ans, j);       int x = pos[j].first;       int y = pos[j].second;       rem(j);       can.erase(j);       id.erase(pos[j]);       for (int z = -2; z < 3; z++) {         if (id.count({x, y + z})) can.erase(id[{x, y + z}]);         if (id.count({x - 1, y + z})) can.erase(id[{x - 1, y + z}]);       }       for (int z = -2; z < 3; z++) {         if (id.count({x, y + z}) && canrem(id[{x, y + z}]))           can.insert(id[{x, y + z}]);         x--;         if (id.count({x, y + z}) && canrem(id[{x, y + z}]))           can.insert(id[{x, y + z}]);         x++;       }     }     cout << ans;     return 0;   }   