length клеток. Её мостят плитками двух видов: прямоугольником 2×1 (две клетки) и уголком из трёх клеток в форме буквы «Г». Плитки можно поворачивать как угодно.
Сколькими способами можно замостить всю дорожку так, чтобы каждая клетка была покрыта ровно одной плиткой? Два способа считаются разными, если найдутся две соседние по стороне клетки, которые в одном способе покрыты одной плиткой, а в другом — разными.
Ответ может быть большим, верните его по модулю 10⁹ + 7.length=2 → 2
Две плитки 2×1 можно положить обе вертикально или обе горизонтально — 2 способа. Уголки в полосу 2×2 без дыр не помещаются.
length=3 → 5
Три способа только из прямоугольников и ещё два — из пары уголков, вставленных друг в друга. Всего 5.
length=5 → 24
length ≤ 1000length=2
2
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 33 теста на сервере, включая скрытые.