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 10^9 + 9.


-----Input-----

The first line contains number m (2 ≤ m ≤ 10^5).

The following m lines contain the coordinates of the cubes x_{i}, y_{i} ( - 10^9 ≤ x_{i} ≤ 10^9, 0 ≤ y_{i} ≤ 10^9) 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

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'import heapq\n\ndef coor_neighbor(coor, dxs, dys):\n    x, y = coor\n    for dx in dxs:\n        for dy in dys:\n            yield x + dx, y + dy\n\n\ndef coor_bottoms(coor):\n    return coor_neighbor(coor, (-1, 0, 1), (-1, ))\n\n\ndef coor_tops(coor):\n    return coor_neighbor(coor, (-1, 0, 1), (1, ))\n\n\ndef coor_sibs(coor):\n    return coor_neighbor(coor, (-2, -1, 1, 2), (0, ))\n\n\nclass Figure:\n\n    def __init__(self, coors):\n        self._coors = dict()\n        self._stables_min = []\n        self._stables_max = []\n        self._pushed = set()\n        self._dropped = set()\n\n        cubes = dict()\n        self._bots = dict()\n        self._tops = dict()\n        for idx, coor in enumerate(coors):\n            cubes[coor] = idx\n            self._coors[idx] = coor\n            self._bots[idx] = set()\n            self._tops[idx] = set()\n\n        coor_set = set(coors)\n        for idx, coor in enumerate(coors):\n            for bottom in coor_bottoms(coor):\n                if bottom in coor_set:\n                    self._bots[idx].add(cubes[bottom])\n            for top in coor_tops(coor):\n                if top in coor_set:\n                    self._tops[idx].add(cubes[top])\n\n        for idx in self._coors:\n            if self.isdroppable(idx):\n                self.push(idx)\n\n    def sibs(self, idx):\n        for top_idx in self._tops[idx]:\n            for sib_idx in self._bots[top_idx]:\n                if sib_idx not in self._dropped:\n                    yield sib_idx\n\n    def bottom_count(self, idx):\n        return len(self._bots[idx])\n\n    def isdroppable(self, idx):\n        return all(len(self._bots[top_idx]) > 1 for top_idx in self._tops[idx])\n\n    def push(self, idx):\n        if idx not in self._pushed:\n            heapq.heappush(self._stables_min, idx)\n            heapq.heappush(self._stables_max, -idx)\n            self._pushed.add(idx)\n\n    def unpush(self, idx):\n        if idx in self._pushed:\n            self._pushed.remove(idx)\n\n    def drop(self, idx):\n        if idx not in self._pushed:\n            return False\n        self._pushed.remove(idx)\n        self._dropped.add(idx)\n\n        for bot_idx in self._bots[idx]:\n            self._tops[bot_idx].remove(idx)\n        for top_idx in self._tops[idx]:\n            self._bots[top_idx].remove(idx)\n\n        coor = self._coors[idx]\n        for bot_idx in self._bots[idx]:\n            if self.isdroppable(bot_idx):\n                self.push(bot_idx)\n        for sib_idx in self.sibs(idx):\n            if not self.isdroppable(sib_idx):\n                self.unpush(sib_idx)\n        return True\n\n    def drop_min(self):\n        while True:\n            if not self._stables_min:\n                return None\n            min_idx = heapq.heappop(self._stables_min)\n            if self.drop(min_idx):\n                return min_idx\n\n    def drop_max(self):\n        while True:\n            if not self._stables_max:\n                return None\n            max_idx = - heapq.heappop(self._stables_max)\n            if self.drop(max_idx):\n                return max_idx\n\n    def __bool__(self):\n        return len(self._coors) != len(self._dropped)\n\n\ndef input_tuple():\n    return tuple(map(int, input().split()))\n\n\ndef result_add(result, base, num):\n    return (result * base + num) % (10 ** 9 + 9)\n\n\nN = int(input())\ncoors = [input_tuple() for _ in range(N)]\n\nfigure = Figure(coors)\nresult = 0\nwhile True:\n    if not figure:\n        break\n    result = result_add(result, N, figure.drop_max())\n    if not figure:\n        break\n    result = result_add(result, N, figure.drop_min())\nprint(result)\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 18307