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<sup class="upper-index">9</sup> + 9.
The first line contains number *m* (2 ≤ *m* ≤ 10<sup class="upper-index">5</sup>).

The following *m* lines contain the coordinates of the cubes *x*<sub class="lower-index">*i*</sub>, *y*<sub class="lower-index">*i*</sub> ( - 10<sup class="upper-index">9</sup> ≤ *x*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">9</sup>, 0 ≤ *y*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">9</sup>) in ascending order of numbers written on them. It is guaranteed that the original figure is stable.

No two cubes occupy the same place.
import heapq

def neighbor(coor, dy):
    x, y = coor
    if y + dy < 0:
        return
    if x - 1 >= 0:
        yield x - 1, y + dy
    yield x, y + dy
    yield x + 1, y + dy


def bottoms(coor):
    return neighbor(coor, -1)


def tops(coor):
    return neighbor(coor, 1)


class Figure:

    def __init__(self, coors):
        self._cubes = {}
        self._stables_min = []
        self._stables_max = []
        self._pushed = set()
        self._dropped = set()

        for idx, coor in enumerate(coors):
            self._cubes[coor] = idx
        for coor, idx in self._cubes.items():
            if self.isdroppable(coor):
                self.push(idx, coor)

    def exist(self, coor):
        return coor in self._cubes and self._cubes[coor] not in self._dropped

    def bottom_count(self, coor):
        return sum(self.exist(bottom) for bottom in bottoms(coor))

    def isstable(self, coor):
        return any(bottom in self._cubes for bottom in bottoms(coor))

    def isdroppable(self, coor):
        return self.exist(coor) and all(
                not self.exist(top) or self.bottom_count(top) > 1
                for top in tops(coor))

    def push(self, idx, coor):
        heapq.heappush(self._stables_min, (idx, coor))
        heapq.heappush(self._stables_max, (-idx, coor))
        self._pushed.add(idx)

    def drop_min(self):
        while True:
            if not self._stables_min:
                return None
            min_cube = heapq.heappop(self._stables_min)
            idx, coor = min_cube
            if idx in self._dropped:
                continue
            self._dropped.add(idx)
            for bottom in bottoms(coor):
                if self.isdroppable(bottom) and self._cubes[bottom] not in self._pushed:
                    self.push(self._cubes[bottom], bottom)
            return idx

    def drop_max(self):
        while True:
            if not self._stables_max:
                return None
            max_cube = heapq.heappop(self._stables_max)
            idx, coor = -max_cube[0], max_cube[1]
            print(idx)
            if idx in self._dropped:
                continue
            self._dropped.add(idx)
            for bottom in bottoms(coor):
                if self.isdroppable(bottom) and self._cubes[bottom] not in self._pushed:
                    self.push(self._cubes[bottom], bottom)
            return idx

    def __bool__(self):
        return bool(len(self._cubes) - len(self._dropped))


def input_tuple():
    return tuple(map(int, input().split()))

N = int(input())
coors = [input_tuple() for _ in range(N)]

figure = Figure(coors)
result = 0
while True:
    if not figure:
        break
    result = (result * N) + figure.drop_max()
    if not figure:
        break
    result = (result * N) + figure.drop_min()
print(result)
