CF520D Cubes

一次，Vasya 和 Petya 用 $m$ 个方块搭建了一个图形。这些方块上被标号为 $0$ 到 $m - 1$。以地面为 $x$ 轴，以垂直向上为正方向建立 $y$ 轴。我们用每个方块左下角的坐标表示它的位置。每个方块的坐标都是整数。 这个图形原本是稳定的。这是指对于每个不是贴在地上的方块，它下方必然存在一个与它相交于一条边或一个角的方块支撑着它。更形式化地说，对于每个方块 $(x, y)$，要么有 $y = 0$，要么存在方块 $(x - 1, y - 1)$，$(x, y - 1)$ 或 $(x + 1, y - 1)$。 现在他们想要拆除这个图形，并吧这些方块一列排开。在一步操作中，一个方块会从图形中被移除，然后被放到已移除的所有方块的最右侧。他们移除方块时，图形仍然是稳定的。 为了使得这个过程更加有意思，Vasya 和 Petya 决定进行如下游戏。他们轮流从图形中取走方块。显然会发现，在图形被完全拆除后，所有方块的编号连起来形成了一个 $m$ 进制的数（可能有前导 $0$）。Vasya 希望这个数尽可能大，而 Petya 正相反，希望这个数尽可能小。Vasya 先手。 你的任务是在两人都采取最优策略的情况下，确定最终形成的数字是多少。输出答案对 $10 ^ 9 + 9$ 取模的结果。

第一行输入一个整数 $m ~ (2 \le m \le 10 ^ 5)$。 接下来 $m$ 行，每行输入两个整数 $x_i, y_i ~ (-10 ^ 9 \le x_i \le 10 ^ 9; 0 \le y_i \le 10 ^ 9)$，按标号递增顺序给出每个方块的坐标。 保证输入的原图是稳定的，且没有两个方块位于相同的位置。

输出一行，表示问题的答案。