B. Кубики
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Как-то раз Вася с Петей собрали конструкцию из m кубиков, на каждом из которых написано число от 0 до m - 1 (каждое число встречалось ровно один раз). Введём систему координат так, что осью OX является земля, а ось OY направлена вверх. Каждый кубик задаётся координатами своего нижнего левого угла, при этом эти координаты целые для каждого кубика.

Конструкция получилась устойчивой. Это значит, что для любого кубика, который не стоит на земле, есть хотя бы один кубик под ним, с которым он касается по стороне или по углу. Более формально, это значит, что для кубика с координатами (x, y) либо выполняется y = 0, либо существует кубик, имеющий координаты (x - 1, y - 1), (x, y - 1) или (x + 1, y - 1).

Теперь мальчики хотят разобрать конструкцию и выложить все кубики в ряд. Очередной кубик удаляется из конструкции и кладется в ряд справа от уже положенных кубиков, при этом ребята вынимают кубики таким образом, что конструкция остаётся устойчивой. Чтобы разнообразить процесс, ребята решили поиграть в следующую игру. Ребята вынимают кубики из конструкции по очереди. Легко видеть, что после разбора конструкции цифры, написанные на кубиках, образуют число, записанное в m-ичной системе счисления (возможно, содержащее ведущий нуль). Вася хочет, чтобы полученное в результате число было наибольшим, а Петя, наоборот, старается его сделать как можно меньше. Вася ходит первым.

Ваша задача — определить, какое число получится после разбора конструкции, если ребята будут действовать оптимально. Определите остаток от деления ответа на 109 + 9.

Входные данные

В первой строке дано число m (2 ≤ m ≤ 105).

В последующих m строках даны координаты кубиков xi, yi ( - 109 ≤ xi ≤ 109, 0 ≤ yi ≤ 109) в порядке следования чисел, написанных на них. Гарантируется, что исходная конструкция устойчива.

Никакие два кубика не совпадают.

Выходные данные

В единственной строке выведите ответ на задачу.

Примеры
Входные данные
3
2 1
1 0
0 1
Выходные данные
19
Входные данные
5
0 0
0 1
0 2
0 3
0 4
Выходные данные
2930