Problem 237

Tours on a 4 x n playing board

Let T(*n*) be the number of tours over a 4 *n* playing board such that:

- The tour starts in the top left corner.
- The tour consists of moves that are up, down, left, or right one square.
- The tour visits each square exactly once.
- The tour ends in the bottom left corner.

The diagram shows one tour over a 4 10 board:

T(10) is 2329. What is T(10^{12}) modulo 10^{8}?

**
These problems are part of
Project Euler
and are licensed under
CC BY-NC-SA 2.0 UK
**