#include <bits/stdc++.h>   using namespace std;   set<int> smax, smin;   int ox[100000], oy[100000];   map<pair<int, int>, int> pnts;   inline int eval(int x, int y) {     if (pnts.count({x, y})) {       return pnts.count({x, y - 1}) + pnts.count({x - 1, y - 1}) +              pnts.count({x + 1, y - 1});     }     return 3;   }   inline bool isOk(int x, int y) {     return (eval(x, y + 1) > 1) && (eval(x - 1, y + 1) > 1) &&            (eval(x + 1, y + 1) > 1);   }   int main() {     ios_base::sync_with_stdio(false);     cin.tie(0);     cerr <<  -.- ;     int m;     cin >> m;     for (int i = 0; i < m; ++i) {       cin >> ox[i] >> oy[i];       pnts.insert({{ox[i], oy[i]}, i});     }     for (int i = 0; i < m; ++i) {       if (isOk(ox[i], oy[i])) {         smax.insert(-i), smin.insert(i);       }     }     int turn = 0;     vector<int> path;     int dd[] = {0, -1, 1, -2, 2};     while (((int)(smax).size())) {       int i = (turn == 0) ? -(*smax.begin()) : (*smin.begin());       smin.erase(i), smax.erase(-i);       path.push_back(i), pnts.erase({ox[i], oy[i]});       for (int d = 1; d < 5; ++d) {         auto it = pnts.find({ox[i] + dd[d], oy[i]});         if (it != pnts.end()) {           int j = it->second;           if (!isOk(ox[j], oy[j])) {             smax.erase(-j), smin.erase(j);           }         }       }       for (int d = 0; d < 3; ++d) {         auto it = pnts.find({ox[i] + dd[d], oy[i] - 1});         if (it != pnts.end()) {           int j = it->second;           if (isOk(ox[j], oy[j])) {             smax.insert(-j), smin.insert(j);           }         }       }       turn ^= 1;     }     int ans = 0;     for (int i = 0; i < ((int)(path).size()); ++i) {       ans = ((1ll * ans * m) + path[i]) % 1000000009;     }     cout << ans <<   n ;     return 0;   }   