The Dunphys are moving into their new residence. But before that they need some remodelling done. Claire, the wife, has handed over the job of remodelling their n x n living-room floor with tiles to Phil, the husband. The two squares at the top-left and bottom-right of the room's floor are occupied by pillars and thus, require no tilling. Phil, being the dim-witted character that he is, has bought peculiarly-sized 2 x 1 tiles. Under the stress of having to face the wrath of Claire, he needs help to figure out the numbers of ways to tile the floor entirely with the 2 x 1 shaped tiles. Can you help him?
The single line of input contains the single integer n.
Print a single line containing a single integer denoting the number of ways the floor can be tilled. Since the answer can be large, output it modulo 1000000007.
2 ≤ n ≤ 16