Рассмотрим замкнутые ломаные, каждая из которых
• проходит через центры всех клеток шахматной доски 4×n,
• состоит из вертикальных и горизонтальных отрезков,
• не имеет самопересечений.
На рисунке изображена одна такая ломаная на доске 4×10:
 
Обозначим через T(n) количество таких ломаных для доски 4×n.
Можно показать, что T(10) = 1517.
Найдите остаток T (10¹²) по модулю 10⁸.