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

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

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

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