A terrace is a grid of 2 rows and n columns. It must be tiled completely, with no gaps or overlaps, using two kinds of tiles: a 1x2 domino (placed horizontally across two cells of a row, or vertically across the two cells of a column) and an L-shaped tromino covering three cells of a 2x2 block (any of its four rotations). 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.
Input format
A single line containing the integer n (the number of columns).
Output format
A single integer: the number of tilings of the 2-by-n terrace, taken modulo 1000000007.
Constraints
- 0 <= n <= 12
- An empty terrace (n = 0) has exactly one tiling: the empty tiling.