Coins

He and she play a game with $N$ coins. The two take turns, and he gave her the first turn. The rules are these.

1. Lay the $N$ coins out in a row. Each coin shows either heads or tails.
2. On your turn, choose one contiguous segment of the row. Every coin in the chosen segment must show heads. You can flip the coins in the segment as you like, deciding for each coin in the segment whether to flip it. At least one coin must be flipped. Once you finish flipping, pass the turn to the other player.
3. A player with no segment to choose on their turn loses. That is, if every coin shows tails when your turn comes, you lose.

Write H for a coin showing heads and T for a coin showing tails, and suppose the coins are laid out as HHHTHH. The player to move has to choose a segment, and no segment containing the fourth coin, which shows tails, can be chosen. A wider segment allows more ways to flip, so choosing coins 1 through 3, or coins 5 through 6, are the meaningful choices. If the first three coins are chosen, the player flips them in one of the $2^3 = 8$ ways minus the one that flips nothing, so one of 7 ways, and passes the turn.

The two keep playing this game. Because both dislike being bored, they pick the starting layout at random every time a game starts, choosing one of the $2^N$ possible layouts with equal probability.

Once a coin is turned to tails there is no way to turn it back to heads, and every turn has to flip at least one coin, so the winner is always decided when both play their best. Assuming both play their best, how many starting layouts let him win?

The first line contains a natural number $N$ ($1 \le N \le 250$), the number of coins.

Print the number of starting layouts that let him win. This number can be very large, so print it modulo 1,000,000,007.