Once Vasya and Petya assembled a figure of m cubes, each of them is associated with a number between 0 and m - 1 (inclusive, each number appeared exactly once). Let's consider a coordinate system such that the OX is the ground, and the OY is directed upwards. Each cube is associated with the coordinates of its lower left corner, these coordinates are integers for each cube.

The figure turned out to be stable. This means that for any cube that is not on the ground, there is at least one cube under it such that those two cubes touch by a side or a corner. More formally, this means that for the cube with coordinates (x, y) either y = 0, or there is a cube with coordinates (x - 1, y - 1), (x, y - 1) or (x + 1, y - 1).

Now the boys want to disassemble the figure and put all the cubes in a row. In one step the cube is removed from the figure and being put to the right of the blocks that have already been laid. The guys remove the cubes in such order that the figure remains stable. To make the process more interesting, the guys decided to play the following game. The guys take out the cubes from the figure in turns. It is easy to see that after the figure is disassembled, the integers written on the cubes form a number, written in the m-ary positional numerical system (possibly, with a leading zero). Vasya wants the resulting number to be maximum possible, and Petya, on the contrary, tries to make it as small as possible. Vasya starts the game.

Your task is to determine what number is formed after the figure is disassembled, if the boys play optimally. Determine the remainder of the answer modulo 109 + 9.

Input

The first line contains number m (2 ≤ m ≤ 105).

The following m lines contain the coordinates of the cubes xi, yi ( - 109 ≤ xi ≤ 109, 0 ≤ yi ≤ 109) in ascending order of numbers written on them. It is guaranteed that the original figure is stable.

No two cubes occupy the same place.

Output

In the only line print the answer to the problem.

Examples

Input

3
2 1
1 0
0 1


Output

19


Input

5
0 0
0 1
0 2
0 3
0 4


Output

2930
import java.io.*;
import java.math.*;
import java.util.*;
import java.util.concurrent.*;

public class P520D {
  final static long MOD = 1_000_000_009L;
  final static int MIN_VALUE = -1_000_000_000 - 1;
  final static int MAX_VALUE = +1_000_000_000 + 1;

  int m;
  TreeSet<Cube> cubes = new TreeSet<Cube>();
  TreeSet<Cube> upper = new TreeSet<Cube>(new Comparator<Cube>() {
    @Override public int compare(Cube cube1, Cube cube2) {
      return ((cube1.v - cube2.v));
    }
  });

  class Cube implements Comparable<Cube> {
    public int x, y, v;
    boolean updated = false;
    Set<Cube> cCubes = new HashSet<Cube>();
    Set<Cube> pCubes = new HashSet<Cube>();

    public Cube(int x, int y, int v) {
      this.x = x;
      this.y = y;
      this.v = v;
    }

    boolean isUpper() {
      for (Cube child : cCubes) {
        if (child.pCubes.size() == 1) { return false; }
      }

      return true;
    }

    void addChild(Cube cube) {
      cCubes.add(cube);
    }

    void removeChild(Cube cube) {
      cCubes.remove(cube);
      if (this.isUpper()) { upper.add(this); }
    }

    void addParent(Cube cube) {
      pCubes.add(cube);
    }

    void removeParent(Cube cube) {
      pCubes.remove(cube);
      for (Cube parent : pCubes) {
        if (!parent.isUpper()) { upper.remove(parent); }
      }
    }

    @Override public int compareTo(Cube cube) {
      return ((y != cube.y) ? (y - cube.y) : (x - cube.x));
    }

    @Override public String toString() {
      String cl = ""; for (Cube cube : cCubes) { cl += cube.v + ","; } cl = (cl.length() > 0) ? cl.substring(0, cl.length() - 1) : cl;
      String pl = ""; for (Cube cube : pCubes) { pl += cube.v + ","; } pl = (pl.length() > 0) ? pl.substring(0, pl.length() - 1) : pl;
      return ("{v = " + v + " ,x=" + x + ",y=" + y + ",c:(" + cl + "),p:(" + pl + ")}");
    }
  }

  void genCubesTree(Cube head) {
    head.updated = true;
    for (Cube cube : cubes.subSet(new Cube((head.v == -1) ? MIN_VALUE : (head.x - 1), head.y + 1, -1),
                                  new Cube((head.v == -1) ? MAX_VALUE : (head.x + 2), head.y + 1, -1))) {
      head.addChild(cube);
      if (head.v >= 0) { cube.addParent(head); }
      if (!cube.updated) { genCubesTree(cube); }
    }
  }

  @SuppressWarnings("unchecked")
  public void run() throws Exception {
    m = nextInt();
    HashMap<Integer, Integer> heights = new HashMap<Integer, Integer>();
int xx = 0;
boolean log = false;
long st = System.currentTimeMillis();

    for (int i = 0; i < m; i++) {
      int x = nextInt();
if ((xx == 0) && (m == 100_000)) xx = x;
      int y = nextInt();
      Integer count = heights.get(y);
      heights.put(y, (count == null) ? 1 : (count + 1));
      cubes.add(new Cube(x, y, i));
    }
//if ((m ==  72_956)/* && (xx == 852_523_908 )*/) { log = true; }
if (log) System.out.println("1: " + (System.currentTimeMillis() - st));
    genCubesTree(new Cube(0, -1, -1));
if (log) System.out.println("2: " + (System.currentTimeMillis() - st));
    
    for (Cube cube : cubes) {
      if (cube.isUpper()) { upper.add(cube); }
    }
if (log) System.out.println("3: " + (System.currentTimeMillis() - st));
if (log) System.out.println("4: " + heights);
if (log) System.out.println("5: " + upper.size());

    boolean isVasya = true;
    long value = 0;
    while (upper.size() > 0) {
//      println("Cubes : " + cubes); pw.flush();
//      println("Upper : " + upper);
//      println("Plaing : " + (isVasya ? "Vasya" : "Petya"));
      Cube taken = (isVasya) ? upper.last() : upper.first();
      
      upper.remove(taken);

      for (Cube cube : taken.pCubes) {
        cube.removeChild(taken);
      }
      for (Cube cube : taken.cCubes) {
        cube.removeParent(taken);
      }
      
      value = (value * m + taken.v) % MOD;

//      println("taken : " + taken); pw.flush(); System.console().readLine();
      isVasya = !isVasya;
    }

    println(value);
  }

  public static void main(String... args) throws Exception {
    br = new BufferedReader(new InputStreamReader(System.in));
    pw = new PrintWriter(new BufferedOutputStream(System.out));
    new P520D().run();
    br.close();
    pw.close();
  }

  static BufferedReader br;
  static PrintWriter pw;
  StringTokenizer stok;

  String nextToken() throws IOException {
    while (stok == null || !stok.hasMoreTokens()) {
      String s = br.readLine();
      if (s == null) { return null; }
      stok = new StringTokenizer(s);
    }
    return stok.nextToken();
  }

  void print(byte b) { print("" + b); }
  void print(int i) { print("" + i); }
  void print(long l) { print("" + l); }
  void print(double d) { print("" + d); }
  void print(char c) { print("" + c); }
  void print(Object o) {
    if (o instanceof int[]) { print(Arrays.toString((int [])o));
    } else if (o instanceof long[]) { print(Arrays.toString((long [])o));
    } else if (o instanceof char[]) { print(Arrays.toString((char [])o));
    } else if (o instanceof byte[]) { print(Arrays.toString((byte [])o));
    } else if (o instanceof short[]) { print(Arrays.toString((short [])o));
    } else if (o instanceof boolean[]) { print(Arrays.toString((boolean [])o));
    } else if (o instanceof float[]) { print(Arrays.toString((float [])o));
    } else if (o instanceof double[]) { print(Arrays.toString((double [])o));
    } else if (o instanceof Object[]) { print(Arrays.toString((Object [])o));
    } else { println("" + o); }
  }
  void print(String s) { pw.print(s); }
  void println() { println(""); }
  void println(byte b) { println("" + b); }
  void println(int i) { println("" + i); }
  void println(long l) { println("" + l); }
  void println(double d) { println("" + d); }
  void println(char c) { println("" + c); }
  void println(Object o) { print(o); println(); }
  void println(String s) { pw.println(s); }
  int nextInt() throws IOException { return Integer.parseInt(nextToken()); }
  long nextLong() throws IOException { return Long.parseLong(nextToken()); }
  double nextDouble() throws IOException { return Double.parseDouble(nextToken()); }
  char nextChar() throws IOException { return (char) (br.read()); }
  String next() throws IOException { return nextToken(); }
  String nextLine() throws IOException { return br.readLine(); }
  int [] readInt(int size) throws IOException {
    int [] array = new int [size];
    for (int i = 0; i < size; i++) { array[i] = nextInt(); }
    return array;
  }
  long [] readLong(int size) throws IOException {
    long [] array = new long [size];
    for (int i = 0; i < size; i++) { array[i] = nextLong(); }
    return array;
  }
  double [] readDouble(int size) throws IOException {
    double [] array = new double [size];
    for (int i = 0; i < size; i++) { array[i] = nextDouble(); }
    return array;
  }
  String [] readLines(int size) throws IOException {
    String [] array = new String [size];
    for (int i = 0; i < size; i++) { array[i] = nextLine(); }
    return array;
  }
}