CF520D.Cubes

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.

有一次，瓦夏和佩佳用 $m$ 个立方体搭成了一座立体图形，每个立方体上标有一个介于 $0$ 到 $m-1$（含）之间的唯一编号（即每个编号恰好出现一次）。我们建立一个坐标系，其中 $OX$ 轴为地面，$OY$ 轴竖直向上。每个立方体以其左下角顶点的坐标表示，且所有立方体的坐标均为整数。

该图形是稳定的。这意味着：对任意一个不在地面上的立方体，其正下方（即 $y$ 坐标小 1 的行）至少存在一个立方体，与它以边或角相接触。更严格地说，对坐标为 $(x, y)$ 的立方体，要么 $y = 0$（即位于地面），要么在坐标 $(x-1, y-1)$、$(x, y-1)$ 或 $(x+1, y-1)$ 处存在另一个立方体。

现在，两个男孩想将该图形完全拆解，并把所有立方体排成一行。每一步中，他们从图形中移除一个立方体，并将其放置在已摆放好的立方体序列的最右端。他们移除立方体的顺序需保证：在每一步操作后，剩余图形仍保持稳定。

为了使过程更有趣，两人决定进行如下游戏：他们轮流移除立方体，瓦夏先手。显然，当图形被完全拆解后，按移除顺序排列的立方体上的数字，便构成一个 $m$ 进制下的 $m$ 位数（允许前导零）。瓦夏希望最终得到的这个 $m$ 进制数尽可能大，而佩佳则希望它尽可能小。

你的任务是：若双方均采取最优策略，求最终形成的 $m$ 进制数；并输出该数对 $10^9 + 9$ 取模的结果。

The first line contains number m (2 ≤ m ≤ 105).

The following m lines contain the coordinates of the cubes x__i, y__i ( - 109 ≤ x__i ≤ 109, 0 ≤ y__i ≤ 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.

第一行包含一个整数 $m$（$2 \leq m \leq 10^5$）。

接下来的 $m$ 行每行包含一个立方体的坐标 $x_i,\,y_i$（$-10^9 \leq x_i \leq 10^9$，$0 \leq y_i \leq 10^9$），这些立方体按其表面所标数字的升序给出。保证原始图形是稳定的。

任意两个立方体不占据同一位置。

In the only line print the answer to the problem.

在唯一的一行中输出问题的答案。