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.*;

/**
 * @author master_j
 * @version 0.4.1
 * @since Mar 22, 2015
 */
public class Solution {
    int n;
    Pair[] indPairMap;
    Map<Pair, Integer> pairIntMap = new TreeMap<>();
    int[] childrenSizes;
    int[] parentsSizes;
    int[][] parents;
    int[][] children;

    private void solve() throws IOException {
        n = io.nI();
        indPairMap = new Pair[n];
        for (int i = 0; i < n; i++) {
            Pair p = new Pair(io.nI(), io.nI());
            indPairMap[i] = p;
            pairIntMap.put(p, i);
        }

        childrenSizes = new int[n];
        children = new int[n][3];

        parentsSizes = new int[n];
        parents = new int[n][3];

        Pair tmp = new Pair(0, 0);
        for (int i = 0; i < n; i++) {
            Integer j;
            Pair p = indPairMap[i];
            tmp.y = p.y - 1;
            tmp.x = p.x - 1;

            j = pairIntMap.get(tmp);
            if (j != null) {
                children[i][childrenSizes[i]++] = j;
                parents[j][parentsSizes[j]++] = i;
            }

            tmp.x++;
            j = pairIntMap.get(tmp);
            if (j != null) {
                children[i][childrenSizes[i]++] = j;
                parents[j][parentsSizes[j]++] = i;
            }

            tmp.x++;
            j = pairIntMap.get(tmp);
            if (j != null) {
                children[i][childrenSizes[i]++] = j;
                parents[j][parentsSizes[j]++] = i;
            }
        }

        int[] ans = new int[n];
        int ansPtr = n;

        int[] t = new int[3];
        boolean first = true;
        boolean[] used = new boolean[n];

        TreeSet<Integer> stables = new TreeSet<>();
        for (int i = 0; i < n; i++)
            updStables(stables, used, i);

        while (!stables.isEmpty()) {
            first ^= true;
            int i = first ? stables.pollFirst() : stables.pollLast();
            used[i] = true;
            ans[--ansPtr] = i;


            int tPtr = 0;
            for (int j = 0; j < parentsSizes[i]; j++)
                t[tPtr++] = parents[i][j];
            remove(i);

            for (int j = 0; j < tPtr; j++)
                for (int k = 0; k < childrenSizes[t[j]]; k++)
                    updStables(stables, used, children[t[j]][k]);

            for (int j = 0; j < childrenSizes[i]; j++) {
                updStables(stables, used, children[i][j]);
            }
        }

//        for (int i : stables)
//            io.wln(i);

        final long MOD = 1_000_000_000 + 9;
        long num = 0L;
        long pow = 1L;
        for (int i : ans) {
            num += pow * i;
            num %= MOD;
            pow *= n;
            pow %= MOD;
        }
        io.wln(num);
//            io.wln(i);

    }//2.2250738585072012e-308

    void updStables(TreeSet<Integer> stables, boolean[] used, int ver) {
        boolean stable = true;
        for (int i = 0; i < parentsSizes[ver]; i++)
            stable &= childrenSizes[parents[ver][i]] >= 2;
        if (stable && !used[ver])
            stables.add(ver);
        if (!stable)
            stables.remove(ver);
    }

    void remove(int i) {
        for (int j = 0; j < childrenSizes[i]; j++)
            removeParent(children[i][j], i);
        for (int j = 0; j < parentsSizes[i]; j++)
            removeChild(parents[i][j], i);
    }

    void removeChild(int ver, int chl) {
        int i;
        for (i = 0; children[ver][i] != chl; i++)
            ;
        for (int j = i; j < children[ver].length - 1; j++)
            children[ver][j] = children[ver][1 + j];
        childrenSizes[ver]--;
    }

    void removeParent(int ver, int anc) {
        int i;
        for (i = 0; parents[ver][i] != anc; i++)
            ;
        for (int j = i; j < parents[ver].length - 1; j++)
            parents[ver][j] = parents[ver][1 + j];
        parentsSizes[ver]--;
    }

    public static void main(String[] args) throws IOException {
        IO.launchSolution(args);
    }

    Solution(IO io) throws IOException {
        this.io = io;
        solve();
    }

    private final IO io;
}

class IO {
    static final String _localArg = "master_j";
    private static final String _problemName = "";
    private static final Mode _inMode = Mode.STD_;
    private static final Mode _outMode = Mode.STD_;
    private static final boolean _autoFlush = false;

    enum Mode {STD_, _PUT_TXT, PROBNAME_}

    private final StreamTokenizer st;
    private final BufferedReader br;
    private final Reader reader;

    private final PrintWriter pw;
    private final Writer writer;

    static void launchSolution(String[] args) throws IOException {
        boolean local = (args.length == 1 && args[0].equals(IO._localArg));
        IO io = new IO(local);

        long nanoTime = 0;
        if (local) {
            nanoTime -= System.nanoTime();
            io.wln("<output>");
        }

        io.flush();
        new Solution(io);
        io.flush();

        if (local) {
            io.wln("</output>");
            nanoTime += System.nanoTime();
            final long D9 = 1000000000, D6 = 1000000, D3 = 1000;
            if (nanoTime >= D9)
                io.wf("%d.%d seconds\n", nanoTime / D9, nanoTime % D9);
            else if (nanoTime >= D6)
                io.wf("%d.%d millis\n", nanoTime / D6, nanoTime % D6);
            else if (nanoTime >= D3)
                io.wf("%d.%d micros\n", nanoTime / D3, nanoTime % D3);
            else
                io.wf("%d nanos\n", nanoTime);
        }

        io.close();
    }

    IO(boolean local) throws IOException {
        if (_inMode == Mode.PROBNAME_ || _outMode == Mode.PROBNAME_)
            if (_problemName.length() == 0)
                throw new IllegalStateException("You imbecile. Where's my <_problemName>?");

        if (_problemName.length() > 0)
            if (_inMode != Mode.PROBNAME_ && _outMode != Mode.PROBNAME_)
                throw new IllegalStateException("You imbecile. What's the <_problemName> for?");

        Locale.setDefault(Locale.US);

        if (local) {
            reader = new FileReader("input.txt");
            writer = new OutputStreamWriter(System.out);
        } else {
            switch (_inMode) {
                case STD_:
                    reader = new InputStreamReader(System.in);
                    break;
                case PROBNAME_:
                    reader = new FileReader(_problemName + ".in");
                    break;
                case _PUT_TXT:
                    reader = new FileReader("input.txt");
                    break;
                default:
                    throw new NullPointerException("You imbecile. Gimme _inMode.");
            }
            switch (_outMode) {
                case STD_:
                    writer = new OutputStreamWriter(System.out);
                    break;
                case PROBNAME_:
                    writer = new FileWriter(_problemName + ".out");
                    break;
                case _PUT_TXT:
                    writer = new FileWriter("output.txt");
                    break;
                default:
                    throw new NullPointerException("You imbecile. Gimme _outMode.");
            }
        }

        br = new BufferedReader(reader);
        st = new StreamTokenizer(br);

        pw = new PrintWriter(writer, _autoFlush);

        if (local && _autoFlush)
            wln("Note: auto-flush is on.");
    }

    //@formatter:off
    void wln()          {pw.println(); }
    void wln(boolean x) {pw.println(x);}
    void wln(char x)    {pw.println(x);}
    void wln(char x[])  {pw.println(x);}
    void wln(double x)  {pw.println(x);}
    void wln(float x)   {pw.println(x);}
    void wln(int x)     {pw.println(x);}
    void wln(long x)    {pw.println(x);}
    void wln(Object x)  {pw.println(x);}
    void wln(String x)  {pw.println(x);}

    void wf(String f, Object... o) {pw.printf(f, o);}

    void w(boolean x)   {pw.print(x);}
    void w(char x) {pw.print(x);}
    void w(char x[]) {pw.print(x);}
    void w(double x)    {pw.print(x);}
    void w(float x)     {pw.print(x);}
    void w(int x)       {pw.print(x);}
    void w(long x)      {pw.print(x);}
    void w(Object x)    {pw.print(x);}
    void w(String x)    {pw.print(x);}

    int nI() throws IOException {st.nextToken(); return (int)st.nval;}
    double nD() throws IOException {st.nextToken(); return st.nval;}
    float nF() throws IOException {st.nextToken(); return (float)st.nval;}
    long nL() throws IOException   {st.nextToken(); return (long)st.nval;}
    String nS() throws IOException {st.nextToken(); return st.sval;}

    int[] nIa(int n) throws IOException {
        int[] a = new int[n];
        for (int i = 0; i < n; i++)
            a[i] = nI();
        return a;
    }
    double[] nDa(int n) throws IOException {
        double[] a = new double[n];
        for (int i = 0; i < n; i++)
            a[i] = nD();
        return a;
    }
    String[] nSa(int n) throws IOException {
        String[] a = new String[n];
        for (int i = 0; i < n; i++)
            a[i] = nS();
        return a;
    }

    void wc(String x)         {wc(x.toCharArray());}
    void wc(char c1, char c2) {for (char c = c1; c<=c2; c++) wc(c);}
    void wc(char x[])         {for (char c : x) wc(c); }
    void wc(char x)           {st.ordinaryChar(x); st.wordChars(x, x);}

    public boolean eof() {return st.ttype == StreamTokenizer.TT_EOF;}
    public boolean eol() {return st.ttype == StreamTokenizer.TT_EOL;}

    void flush() {pw.flush();}
    void close() throws IOException {reader.close(); br.close(); flush(); pw.close();}
    //@formatter:on
}

class Pair implements Comparable<Pair> {
    int x, y;

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

    @Override
    public int compareTo(Pair that) {
        if (that.y != this.y)
            return that.y - this.y;
        else
            return this.x - that.x;
    }

//    static Comparator<Pair> idComp = new Comparator<Pair>() {
//        @Override
//        public int compare(Pair o1, Pair o2) {
//            return o1.id - o2.id;
//        }
//    }
}