← 返回题目列表

Codeforces · 520/D

D. 立方体

中文机器翻译题面 查看原题

一旦 Vasya 和 Petya 组装了一个由 m 个立方体组成的图形,每个立方体都与 0 到 m - 1 之间的数字相关联(包括 0 和 m - 1,每个数字只出现一次)。让我们考虑一个坐标系,其中 OX 为地面,OY 向上。每个立方体都与其左下角的坐标相关联,这些坐标对于每个立方体来说都是整数。

该数字结果稳定。这意味着对于任何不在地面上的立方体,其下方至少有一个立方体,使得这两个立方体的一侧或一个角接触。更正式地说,这意味着对于坐标为 (x, y) 的立方体,要么 y = 0,要么存在坐标为 (x - 1, y - 1)、(x, y - 1) 或 (x + 1, y - 1) 的立方体。

现在男孩们想要拆解这个人物并将所有的立方体排成一排。第一步,将立方体从图中移除,并将其放置在已放置的块的右侧。这些人按照使人物保持稳定的顺序移除立方体。为了让这个过程变得更有趣,大家决定玩下面的游戏。小伙子们轮流从人偶中取出立方体。很容易看出,将图形拆开后,写在立方体上的整数形成一个数字,以 m 进制位置数值系统书写(可能带有前导零)。 Vasya 希望得到的数字尽可能大,而 Petya 相反,试图使其尽可能小。瓦夏开始比赛。

你的任务是确定在孩子们发挥最佳的情况下,人物被分解后会形成什么数字。确定答案对 109 + 9 求模的余数。

输入

第一行包含数字 m (2 ≤ m ≤ 105)。

以下 m 行包含立方体 xi、yi (- 109 ≤ xi ≤ 109, 0 ≤ yi ≤ 109) 的坐标,按其上所写数字的升序排列。保证原图稳定。

没有两个立方体占据相同的位置。

输出

在唯一的一行中打印问题的答案。

示例

输入 #1

3
2 1
1 0
0 1

输出 #1

19

输入 #2

5
0 0
0 1
0 2
0 3
0 4

输出 #2

2930