Once Vasya and Petya assembled a figure ofmcubes, each of them is associated with a number between0andm-1(inclusive, each number appeared exactly once). Let’s consider a coordinate system such that theOXis the ground, and theOYis 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 bestable. 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 touchby a side or a corner. More formally, this means that for the cube with coordinates(x,y)eithery=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 them-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 modulo109+9.
，拥有一颗比九万五千公里还辽阔的心，
