length cells long. It is paved with two kinds of tiles: a 2×1 rectangle (two cells) and an L-shaped corner tile made of three cells. Tiles can be rotated any way you like.
In how many ways can the whole path be paved so that every cell is covered by exactly one tile? Two pavings are different if there are two side-adjacent cells that share a tile in one paving but belong to different tiles in the other.
The answer can be large, so return it modulo 10⁹ + 7.length=2 → 2
Two 2×1 tiles go either both upright or both lengthwise: 2 ways. Corner tiles cannot fill a 2×2 strip without gaps.
length=3 → 5
Three layouts use only rectangles, and two more interlock a pair of corner tiles. 5 in total.
length=5 → 24
length ≤ 1000length=2
2
Run checks the first 3 tests in your browser. Submit checks all 33 tests on the server, hidden ones included.