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.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Random;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class _520D {

    static final int MOD = 1000000009;
    static int n;
    static int[] x, y;
    static int[] rank;
    static boolean[] hasCube;
    static Random rand = new Random();

    static boolean isSafeToRemove(int u) {
        int xx = x[u], yy = y[u];
        for (int i = -1; i <= 1; i++) {
            int v = find(xx + i, yy + 1);
            if (v == -1 || !hasCube[v]) continue;

            boolean ok = false;
            for (int j = -1; j <= 1; j++) {
                if (xx + i + j == xx) continue;
                v = find(xx + i + j, yy);
                if (v != -1 && hasCube[v]) {
                    // require x + i + j because (x, y) needs to be removed
                    ok = true;
                    break;
                }
            }
            if (!ok) return false;
        }
        return true;
    }

    static int cmp(int i, int j) {
        if (x[i] < x[j]) return -1;
        else if (x[i] > x[j]) return 1;
        else if (y[i] < y[j]) return -1;
        else if (y[i] > y[j]) return 1;
        else return 0;
    }

    static int cmp(int index, int xx, int yy) {
        if (x[index] < xx) return -1;
        else if (x[index] > xx) return 1;
        else if (y[index] < yy) return -1;
        else if (y[index] > yy) return 1;
        else return 0;
    }

    static void sort(int[] a, int l, int r) {
        int i = l, j = r, x = a[rand.nextInt(r - l + 1) + l];
        do {
            while (cmp(a[i], x) < 0)
                i++;
            while (cmp(a[j], x) > 0)
                j--;
            if (i <= j) {
                ArrayUtil.swap(a, i, j);
                i++;
                j--;
            }
        } while (i <= j);
        if (i < r) sort(a, i, r);
        if (j > l) sort(a, l, j);
    }

    static int find(int x, int y) {
        int left = 0, right = n - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            int res = cmp(rank[mid], x, y);
            if (res == 0) return rank[mid];
            else if (res < 0) left = mid + 1;
            else right = mid - 1;
        }
        return -1;
    }

    public static void main(String[] args) throws Exception {
        Reader.init(System.in);
        BufferedWriter cout = new BufferedWriter(new OutputStreamWriter(System.out));

        n = Reader.nextInt();
        x = new int[n];
        y = new int[n];
        rank = new int[n];

        hasCube = new boolean[n];
        for (int i = 0; i < n; i++) {
            x[i] = Reader.nextInt();
            y[i] = Reader.nextInt();
            hasCube[i] = true;
        }
        for (int i = 0; i < n; i++)
            rank[i] = i;
        sort(rank, 0, n - 1);

        long ans = 0;
        // Now perform a bfs
        TreeSet<Integer> queue = new TreeSet<>();
        for (int u = 0; u < n; u++)
            if (isSafeToRemove(u)) queue.add(u);
        //        System.out.println(queue);
        int round = 0;
        while (!queue.isEmpty()) {
            int u = round % 2 == 0 ? queue.pollLast() : queue.pollFirst();
            round++;
            ans = (ans * n + u) % MOD;
            hasCube[u] = false;

            for (int delta = -1; delta <= 1; delta++) {
                int v = find(x[u] + delta, y[u] - 1);
                if (v != -1 && hasCube[v] && !queue.contains(v) && isSafeToRemove(v)) queue.add(v);
            }
            for (int delta = -2; delta <= 2; delta++) {
                if (delta == 0) continue;
                int v = find(x[u] + delta, y[u]);
                if (v != -1 && hasCube[v] && queue.contains(v) && !isSafeToRemove(v)) queue.remove(v);
            }
        }

        System.out.println(ans);

        cout.close();
    }

    static class Pair<U extends Comparable<U>, V extends Comparable<V>> implements Comparable<Pair<U, V>> {
        final U _1;
        final V _2;

        private Pair(U key, V val) {
            this._1 = key;
            this._2 = val;
        }

        public static <U extends Comparable<U>, V extends Comparable<V>> Pair<U, V> instanceOf(U _1, V _2) {
            return new Pair<U, V>(_1, _2);
        }

        @Override
        public String toString() {
            return _1 + " " + _2;
        }

        @Override
        public int hashCode() {
            int res = 17;
            res = res * 31 + _1.hashCode();
            res = res * 31 + _2.hashCode();
            return res;
        }

        @Override
        public int compareTo(Pair<U, V> that) {
            int res = this._1.compareTo(that._1);
            if (res < 0 || res > 0) return res;
            else return this._2.compareTo(that._2);
        }

        @Override
        public boolean equals(Object obj) {
            if (this == obj) return true;
            if (!(obj instanceof Pair)) return false;
            Pair<?, ?> that = (Pair<?, ?>) obj;
            return _1.equals(that._1) && _2.equals(that._2);
        }
    }

    /** Class for buffered reading int and double values */
    static class Reader {
        static BufferedReader reader;
        static StringTokenizer tokenizer;

        /** call this method to initialize reader for InputStream */
        static void init(InputStream input) {
            reader = new BufferedReader(new InputStreamReader(input));
            tokenizer = new StringTokenizer("");
        }

        /** get next word */
        static String next() throws IOException {
            while (!tokenizer.hasMoreTokens()) {
                // TODO add check for eof if necessary
                tokenizer = new StringTokenizer(reader.readLine());
            }
            return tokenizer.nextToken();
        }

        static int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        static double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }
    }

    static class ArrayUtil {
        static void swap(int[] a, int i, int j) {
            int tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }

        static void swap(long[] a, int i, int j) {
            long tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }

        static void swap(double[] a, int i, int j) {
            double tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }

        static void swap(char[] a, int i, int j) {
            char tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }

        static void swap(boolean[] a, int i, int j) {
            boolean tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }

        static void reverse(int[] a, int i, int j) {
            for (; i < j; i++, j--)
                swap(a, i, j);
        }

        static void reverse(long[] a, int i, int j) {
            for (; i < j; i++, j--)
                swap(a, i, j);
        }

        static void reverse(double[] a, int i, int j) {
            for (; i < j; i++, j--)
                swap(a, i, j);
        }

        static void reverse(char[] a, int i, int j) {
            for (; i < j; i++, j--)
                swap(a, i, j);
        }

        static void reverse(boolean[] a, int i, int j) {
            for (; i < j; i++, j--)
                swap(a, i, j);
        }

        static long sum(int[] a) {
            int sum = 0;
            for (int i : a)
                sum += i;
            return sum;
        }

        static long sum(long[] a) {
            long sum = 0;
            for (long i : a)
                sum += i;
            return sum;
        }

        static double sum(double[] a) {
            double sum = 0;
            for (double i : a)
                sum += i;
            return sum;
        }

        static int max(int[] a) {
            int max = Integer.MIN_VALUE;
            for (int i : a)
                if (i > max) max = i;
            return max;
        }

        static int min(int[] a) {
            int min = Integer.MAX_VALUE;
            for (int i : a)
                if (i < min) min = i;
            return min;
        }

        static long max(long[] a) {
            long max = Long.MIN_VALUE;
            for (long i : a)
                if (i > max) max = i;
            return max;
        }

        static long min(long[] a) {
            long min = Long.MAX_VALUE;
            for (long i : a)
                if (i < min) min = i;
            return min;
        }
    }
}
