Задача на динамическое программирование: Замощение домино и тримино

У вас есть два вида плиток:

домино — прямоугольник 2 × 1;

тримино — L-образная плитка, состоящая из трёх клеток.

Обе плитки можно свободно поворачивать.

По данному целому n определите, сколькими способами можно замостить доску 2×n этими плитками. Поскольку ответ может быть очень большим, выведите его по модулю 10^9 + 7.

Замощением считается такое покрытие, при котором каждая клетка доски закрыта плиткой. Два замощения считаются разными, если существует пара клеток, соприкасающихся сторонами, которые в одном замощении укрыты одной плиткой, а в другом — двумя разными.

Например, для n = 3 таких замощений 5, как показано на картинке

Ссылка на leetcode: https://leetcode.com/problems/domino-and-tromino-tiling

Решение описал тут: Замощение домино и тримино