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

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

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

T(10) равно 2329. Чему равно T(10¹²) mod 10⁸?