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.util.*;
import java.math.BigInteger;

public class Main{
    final boolean isFileIO =  false;
    BufferedReader in;
    PrintWriter out;
    StringTokenizer st = new StringTokenizer("");
    String delim = " ";

    public static void main(String[] args) throws IOException {
        Main m = new Main();
        m.initIO();
        m.solve();
        m.in.close();
        m.out.close();
    }

    public void initIO() throws IOException {
        if(!isFileIO) {
            in = new BufferedReader(new InputStreamReader(System.in));
            out = new PrintWriter(System.out);
        } else {
            in = new BufferedReader(new FileReader("input.txt"));
            out = new PrintWriter("output.txt");
        }
    }

    String nt() throws IOException {
        if(!st.hasMoreTokens()) {
            st = new StringTokenizer(in.readLine());
        }
        return st.nextToken(delim);
    }

    String rl() throws IOException {
        return in.readLine();
    }

    int ni() throws IOException {
        return Integer.parseInt(nt());
    }

    long nl() throws IOException {
        return Long.parseLong(nt());
    }

    double nd() throws IOException {
        return Double.parseDouble(nt());
    }

    class Pair {
        public int x;
        public int y;

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

        public String toString() {
            return String.format("{%d, %d}", x, y);
        }
    }

    class Cube {
        public int x, y, v;
        public boolean u;
        public Cube(int x, int y, int v) {
            this.x = x;
            this.y = y;
            this.v = v;
        }
        public String toString() {
            return String.format("%d", v);
        }
    }
    HashMap<Integer, HashMap<Integer, Cube>> map;
    TreeSet<Cube> safe;
    public void solve() throws IOException {
        int m = ni();
        map = new HashMap<Integer, HashMap<Integer, Cube>>();
        safe = new TreeSet<Cube>(new Comparator<Cube>() {
            @Override
            public int compare(Cube o1, Cube o2) {
                if(o1.v > o2.v) {
                    return -1;
                }
                if(o1.v < o2.v) {
                    return 1;
                }
                return 0;
            }
        });
        Cube[] cubes = new Cube[m];
        for(int i = 0; i < m; i++) {
            cubes[i] = new Cube(ni(), ni(), i);
            if(map.containsKey(cubes[i].y)) {
                map.get(cubes[i].y).put(cubes[i].x, cubes[i]);
            } else {
                map.put(cubes[i].y, new HashMap<Integer, Cube>());
                map.get(cubes[i].y).put(cubes[i].x, cubes[i]);
            }
        }
        for(int i = 0; i < m; i++) {
            if(cntOfDependent(cubes[i]) == 0) {
                safe.add(cubes[i]);
            }
        }
        long mod = 1000000009;
        ArrayList<Integer> ans = new ArrayList<Integer>();

        for(int i = 0; i < m; i++) {
            Cube cube = null;
            if(i % 2 == 0) {
                cube = safe.pollFirst();
            } else {
                cube = safe.pollLast();
            }
            cube.u = true;
            checkParents(cube);
            checkAdj(cube);
            ans.add(cube.v);
        }
        long res = 0;
        long pow = 1;
        for(int i = ans.size() - 1; i >= 0; i--) {
            res = (res + ans.get(i) * pow) % mod;
            pow = (pow * m) % mod;
        }
        out.println(res);
    }

    void checkParents(Cube cube) {
        int x = cube.x;
        int y = cube.y;
        if(!map.containsKey(y - 1)) {
            return;
        }
        HashMap<Integer, Cube> lowMap = map.get(y - 1);
        for(int i = -1; i <= 1; i++) {
            Cube lowCube = lowMap.get(x + i);
            if(lowCube == null || lowCube.u) {
                continue;
            }
            if(cntOfDependent(lowCube) == 0) {
                safe.add(lowCube);
            }
        }
    }

    void checkAdj(Cube cube) {
        int x = cube.x;
        int y = cube.y;
        if(!map.containsKey(y + 1)) {
            return;
        }
        HashMap<Integer, Cube> upMap = map.get(y + 1);
        if(upMap == null) {
            return;
        }
        for(int i = -1; i <= 1; i++) {
            Cube upCube = upMap.get(x + i);
            if(upCube == null || upCube.u) {
                continue;
            }
            Cube base = getBase(upCube);
            if(base!= null) {
                if(safe.contains(base)) {
                    safe.remove(base);
                }
            }
        }
    }

    Cube getBase(Cube cube) {
        int x = cube.x;
        int y = cube.y;
        if(!map.containsKey(y - 1)) {
            return null;
        }
        HashMap<Integer, Cube> lowMap = map.get(y - 1);
        Cube ans = null;
        int cnt = 0;
        for(int i = -1; i <= 1; i++) {
            Cube lowCube = lowMap.get(x + i);
            if(!(lowCube == null || lowCube.u)) {
                cnt++;
                ans = lowCube;
            }
        }
        if(cnt == 1) {
            return ans;
        } else {
            return null;
        }
    }

    int cntOfDependent(Cube cube) {
        int x = cube.x;
        int y = cube.y;
        if(!map.containsKey(y + 1)) {
            return 0;
        }
        int ans = 0;
        HashMap<Integer, Cube> upMap = map.get(y + 1);
        for(int i = -1; i <= 1; i++) {
            Cube upCube = upMap.get(x + i);
            if(upCube == null || upCube.u) {
                continue;
            }
            if(cntOfLower(upCube) == 1) {
                ans++;
            }
        }
        return ans;
    }

    int cntOfLower(Cube cube) {
        int x = cube.x;
        int y = cube.y;
        if(!map.containsKey(y - 1)) {
            return 0;
        }
        int ans = 0;
        HashMap<Integer, Cube> lowMap = map.get(y - 1);
        for(int i = -1; i <= 1; i++) {
            Cube lowCube = lowMap.get(x + i);
            if(lowCube == null || lowCube.u) {
                continue;
            }
            ans++;
        }
        return ans;
    }
}

class Utils {

    public static long binpow(long a, long exp, long mod) {
        if(exp == 0) {
            return 1;
        }
        if(exp % 2 == 0) {
            long temp = binpow(a, exp / 2, mod);
            return (temp * temp) % mod;
        } else {
            return (binpow(a, exp - 1, mod) * a) % mod;
        }
    }

    public static long inv(long a, long mod) {
        return binpow(a, mod - 2, mod);
    }

    public static long addmod(long a, long b, long mod) {
        return ((a + b) % mod + mod) % mod;
    }

    public static long gcd(long a, long b) {
        if(b == 0)
            return a;
        return gcd(b, a % b);
    }

    //mul must be < 10^18
    public static long mulmod(long a, long b, long mod) {
        return (a * b + (((a * b) / mod) + 1) * mod) % mod;
    }
}