Кусок бумаге в форме квадрата с целыми сторонами N×N помещается в начало координат, а его стороны - вдоль x-оси и y-оси. Затем, мы разрезаем этот квадрат, руководствуясь следующими правилами:

• Позволяется разрезать только по прямой между двумя точками на разных сторонах квадрата, при этом координаты точек должны быть целыми числами.
• Два разреза не должны пересекаться, но допустимо, чтобы они исходили из одной и той же точки на стороне квадрата.
• Продолжайте разрезать квадратик, до тех пор, пока это возможно.

Считая все варианты отражения и поворота различающимися, обозначим через C(N) количество способов разрезания квадрата размерами N×N. К примеру, C(1) = 2 и C(2) = 30 (показано ниже).

Чему равно C(30) mod 10⁸ ?