An atrium floor is a grid of 2 rows and n columns. It is to be tiled completely, without gaps or overlaps, using two kinds of tiles: a 1x2 domino (which may be placed horizontally covering two cells in a row, or vertically covering the two cells of one column) and a 2x2 square tile (covering a full pair of adjacent columns). Two tilings are different if any cell is covered by a differently placed or differently shaped tile.
Count the number of distinct complete tilings. Print the count modulo 1000000007.
A single line containing the integer n (the number of columns).
A single integer: the number of tilings of the 2-by-n floor, taken modulo 1000000007.
Example 1
Input
2
Expected
3
Explanation
A 2x2 floor can be two vertical dominoes, two horizontal dominoes, or one square tile: 3 tilings.
Example 2
Input
3
Expected
5
Explanation
A 2x3 floor has 5 tilings, obtained by extending each 2x2 tiling with a vertical domino, plus the arrangements that straddle the columns.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →