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.
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 floor, taken modulo 1000000007.
Constraints
- 0 <= n <= 12
- An empty floor (n = 0) has exactly one tiling: the empty tiling.