You have a board that is 2 rows tall and n columns wide. You want to cover every cell exactly once using 2x1 dominoes; each domino may be placed either vertically (covering both rows of one column) or horizontally (covering one row across two adjacent columns).
Count the number of distinct full tilings. Because the count grows quickly, report it modulo 1000000007.
A single line containing the integer n.
A single integer: the number of tilings modulo 1000000007.
Example 1
Input
1
Expected
1
Explanation
A 2x1 board is covered in exactly one way: a single vertical domino.
Example 2
Input
3
Expected
3
Explanation
A 2x3 board has 3 tilings: all vertical, or a vertical column beside a 2x2 block of two horizontal dominoes (on the left or on the right).
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 →