Задача 237
Путешествия по доске 4 x n

Пусть T(n) будет количеством маршрутов по доске 4 × n таких, что:

  • Маршрут начинается в левом верхнем углу.
  • Маршрут состоит из движений вверх, вниз, влево или вправо на одну клетку.
  • Маршрут проходит по каждой клетке ровно один раз.
  • Маршрут кончается в нижнем левом углу.

Рисунок ниже показывает один из маршрутов по доске 4 × 10:

T(10) равно 2329. Чему равно T(10^(12)) mod 10^(8)?

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