#include <bits/stdc++.h>
int x[101000], y[101000], c[101000];
long long anss[101000];
int tempa[101000], tempb[101000], tempc[101000];
int l[101000][10];
int in[101000];
int he[2][101000], wh[2][101000];
int nhh[2];
int zhh[2] = {1, -1};
void mergesort(int *a, int *b, int *c, int n1, int n2);
int ya(int k) {
  int z;
  int tempk;
  int i;
  if (l[k][0]) {
    z = 1;
    for (i = 4; i <= 6; i++) {
      tempk = l[k][i];
      if ((l[tempk][0]) &&
          (l[l[tempk][1]][0] + l[l[tempk][2]][0] + l[l[tempk][3]][0] == 1)) {
        z = 0;
        break;
      }
    }
    return z;
  } else {
    z = 0;
  }
  return z;
}
void push(int k) {
  int i;
  int nh, zh;
  int p;
  for (i = 0; i <= 1; i++) {
    zh = zhh[i];
    nh = nhh[i];
    p = ++nh;
    while (p > 1) {
      if (c[k] * zh < c[he[i][p >> 1]] * zh) {
        he[i][p] = he[i][p >> 1];
        wh[i][he[i][p]] = p;
        p >>= 1;
      } else {
        break;
      }
    }
    he[i][p] = k;
    wh[i][k] = p;
    nhh[i] = nh;
  }
}
int pop(int k) {
  int i, ii;
  int k2;
  int nh, zh;
  int p;
  if (k < 0) {
    if (k == -1) {
      i = 1;
      ii = 0;
    } else {
      i = 0;
      ii = 1;
    }
    k = he[i][1];
    nh = nhh[i];
    zh = zhh[i];
    k2 = he[i][nh];
    nh--;
    p = 1;
    while (p + p + 1 <= nh) {
      if (c[he[i][p + p]] * zh <= c[he[i][p + p + 1]] * zh &&
          c[he[i][p + p]] * zh < c[k2] * zh) {
        he[i][p] = he[i][p + p];
        wh[i][he[i][p]] = p;
        p = p + p;
      } else if (c[he[i][p + p]] * zh > c[he[i][p + p + 1]] * zh &&
                 c[he[i][p + p + 1]] * zh < c[k2] * zh) {
        he[i][p] = he[i][p + p + 1];
        wh[i][he[i][p]] = p;
        p = p + p + 1;
      } else {
        break;
      }
    }
    if (p + p <= nh && c[he[i][p + p]] * zh < c[k2] * zh) {
      he[i][p] = he[i][p + p];
      wh[i][he[i][p]] = p;
      p = p + p;
    }
    he[i][p] = k2;
    wh[i][k2] = p;
    nhh[i] = nh;
    i = ii;
    p = wh[i][k];
    zh = zhh[i];
    nh = nhh[i];
    k2 = he[i][nh];
    nh--;
    while (p > 1) {
      if (c[k2] * zh < c[he[i][p >> 1]] * zh) {
        he[i][p] = he[i][p >> 1];
        wh[i][he[i][p]] = p;
        p >>= 1;
      } else {
        break;
      }
    }
    while (p + p + 1 <= nh) {
      if (c[he[i][p + p]] * zh <= c[he[i][p + p + 1]] * zh &&
          c[he[i][p + p]] * zh < c[k2] * zh) {
        he[i][p] = he[i][p + p];
        wh[i][he[i][p]] = p;
        p = p + p;
      } else if (c[he[i][p + p]] * zh > c[he[i][p + p + 1]] * zh &&
                 c[he[i][p + p + 1]] * zh < c[k2] * zh) {
        he[i][p] = he[i][p + p + 1];
        wh[i][he[i][p]] = p;
        p = p + p + 1;
      } else {
        break;
      }
    }
    if (p + p <= nh && c[he[i][p + p]] * zh < c[k2] * zh) {
      he[i][p] = he[i][p + p];
      wh[i][he[i][p]] = p;
      p = p + p;
    }
    he[i][p] = k2;
    wh[i][k2] = p;
    nhh[i] = nh;
    return k;
  } else {
    for (i = 0; i <= 1; i++) {
      p = wh[i][k];
      zh = zhh[i];
      nh = nhh[i];
      k2 = he[i][nh];
      nh--;
      while (p > 1) {
        if (c[k2] * zh < c[he[i][p >> 1]] * zh) {
          he[i][p] = he[i][p >> 1];
          wh[i][he[i][p]] = p;
          p >>= 1;
        } else {
          break;
        }
      }
      while (p + p + 1 <= nh) {
        if (c[he[i][p + p]] * zh <= c[he[i][p + p + 1]] * zh &&
            c[he[i][p + p]] * zh < c[k2] * zh) {
          he[i][p] = he[i][p + p];
          wh[i][he[i][p]] = p;
          p = p + p;
        } else if (c[he[i][p + p]] * zh > c[he[i][p + p + 1]] * zh &&
                   c[he[i][p + p + 1]] * zh < c[k2] * zh) {
          he[i][p] = he[i][p + p + 1];
          wh[i][he[i][p]] = p;
          p = p + p + 1;
        } else {
          break;
        }
      }
      if (p + p <= nh && c[he[i][p + p]] * zh < c[k2] * zh) {
        he[i][p] = he[i][p + p];
        wh[i][he[i][p]] = p;
        p = p + p;
      }
      he[i][p] = k2;
      wh[i][k2] = p;
      nhh[i] = nh;
    }
  }
}
int main(void) {
  int n, i, j;
  long long mod = 1000000009;
  long long ans;
  int p1, p2;
  int k, tempk;
  while (scanf("%d", &n) != EOF) {
    anss[n] = 1;
    for (i = n - 1; i; i--) {
      anss[i] = (anss[i + 1] * n) % mod;
    }
    for (i = 1; i <= n; i++) {
      scanf("%d %d", &x[i], &y[i]);
      c[i] = i - 1;
    }
    mergesort(y, x, c, 1, n);
    for (j = 0; j <= 6; j++) {
      l[0][j] = 0;
    }
    p1 = 1;
    p2 = 1;
    for (i = 1; i <= n; i++) {
      l[i][0] = 1;
      for (j = 1; j <= 6; j++) {
        l[i][j] = 0;
      }
      for (j = p1; j <= n;) {
        if (y[j] < y[i] - 1) {
          j++;
        } else if (y[j] == y[i] - 1) {
          if (x[j] < x[i] - 1) {
            j++;
          } else if (x[j] == x[i] - 1) {
            l[i][1] = j;
            j++;
          } else if (x[j] == x[i]) {
            l[i][2] = j;
            j++;
          } else if (x[j] == x[i] + 1) {
            l[i][3] = j;
            j++;
          } else {
            break;
          }
        } else {
          break;
        }
      }
      p1 = j - 2;
      if (p1 <= 0) {
        p1 = 1;
      }
      for (j = p2; j <= n;) {
        if (y[j] <= y[i]) {
          j++;
        } else if (y[j] == y[i] + 1) {
          if (x[j] < x[i] - 1) {
            j++;
          } else if (x[j] == x[i] - 1) {
            l[i][4] = j;
            j++;
          } else if (x[j] == x[i]) {
            l[i][5] = j;
            j++;
          } else if (x[j] == x[i] + 1) {
            l[i][6] = j;
            j++;
          } else {
            break;
          }
        } else {
          break;
        }
      }
      p2 = j - 2;
      if (p2 <= 0) {
        p2 = 1;
      }
    }
    nhh[0] = 0;
    nhh[1] = 0;
    for (i = 1; i <= n; i++) {
      in[i] = 0;
      if (ya(i)) {
        push(i);
        in[i] = 1;
      }
    }
    ans = 0;
    in[0] = 0;
    for (i = 1; i <= n; i++) {
      k = pop((i & 1) - 2);
      in[k] = 0;
      l[k][0] = 0;
      ans = (ans + anss[i] * c[k]) % mod;
      for (j = 1; j <= 3; j++) {
        tempk = l[k][j];
        if (ya(tempk) && !in[tempk]) {
          push(tempk);
          in[tempk] = 1;
        }
      }
      tempk = l[l[k][4]][1];
      if (!ya(tempk) && in[tempk]) {
        pop(tempk);
        in[tempk] = 0;
      }
      tempk = l[l[k][4]][2];
      if (!ya(tempk) && in[tempk]) {
        pop(tempk);
        in[tempk] = 0;
      }
      tempk = l[l[k][6]][2];
      if (!ya(tempk) && in[tempk]) {
        pop(tempk);
        in[tempk] = 0;
      }
      tempk = l[l[k][6]][3];
      if (!ya(tempk) && in[tempk]) {
        pop(tempk);
        in[tempk] = 0;
      }
      if (!l[l[k][4]][0]) {
        tempk = l[l[k][5]][1];
        if (!ya(tempk) && in[tempk]) {
          pop(tempk);
          in[tempk] = 0;
        }
      }
      if (!l[l[k][6]][0]) {
        tempk = l[l[k][5]][3];
        if (!ya(tempk) && in[tempk]) {
          pop(tempk);
          in[tempk] = 0;
        }
      }
    }
    printf("%I64d\n", ans);
  }
  return 0;
}
void mergesort(int *a, int *b, int *c, int n1, int n2) {
  int a1, a2, n12;
  int i, j;
  if (n1 < n2) {
    n12 = (n1 + n2) / 2;
    mergesort(a, b, c, n1, n12);
    mergesort(a, b, c, n12 + 1, n2);
    for (i = n1; i <= n2; i++) {
      tempa[i] = a[i];
      tempb[i] = b[i];
      tempc[i] = c[i];
    }
    a1 = n1;
    a2 = n12 + 1;
    for (i = n1; (a1 <= n12 && a2 <= n2); i++) {
      if (tempa[a1] < tempa[a2] ||
          (tempa[a1] == tempa[a2] && tempb[a1] <= tempb[a2])) {
        a[i] = tempa[a1];
        b[i] = tempb[a1];
        c[i] = tempc[a1];
        a1++;
      } else {
        a[i] = tempa[a2];
        b[i] = tempb[a2];
        c[i] = tempc[a2];
        a2++;
      }
    }
    if (a1 > n12) {
      for (j = a2; j <= n2; j++, i++) {
        a[i] = tempa[j];
        b[i] = tempb[j];
        c[i] = tempc[j];
      }
    } else {
      for (j = a1; j <= n12; j++, i++) {
        a[i] = tempa[j];
        b[i] = tempb[j];
        c[i] = tempc[j];
      }
    }
  }
}
