Задача 270
Разрезание квадратиков

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

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

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

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

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net