Сколько способов вы можете выложить прямоугольник 3xn домино 2x1?

Каждый день я борюсь с вопросами алгоритмов и пытаюсь задать здесь вопросы, на которые я не могу ответить. Простите, если у меня болит голова. В любом случае,

Вот задача из конкурса программирования ACM Университета Ватерлоо.

Какими способами можно выложить прямоугольник 3xn домино 2x1?

Нирвана: пахнет ] recursion spirit