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.
Input format
A single line containing the integer n.
Output format
A single integer: the number of tilings modulo 1000000007.
Constraints
- 1 <= n <= 100000