동전

그와 그녀가 동전 $N$개로 게임을 한다. 두 사람이 번갈아 진행하며, 그는 첫 차례를 그녀에게 양보했다. 규칙은 다음과 같다.

1. 동전 $N$개를 일렬로 늘어놓는다. 각 동전은 앞면이나 뒷면이 위를 향한다.
2. 자기 차례가 오면 일렬로 늘어선 동전에서 연속한 구간 하나를 고른다. 고른 구간의 동전은 모두 앞면이어야 한다. 구간 안의 동전은 마음대로 뒤집을 수 있다. 즉 구간에 속한 동전마다 뒤집을지 말지 스스로 정한다. 다만 적어도 한 개는 뒤집어야 한다. 다 뒤집고 나면 차례를 상대에게 넘긴다.
3. 자기 차례에 고를 구간이 없는 사람이 진다. 즉 모든 동전이 뒷면인 상태로 차례를 받으면 진다.

앞면이 위를 향하면 H, 뒷면이 위를 향하면 T로 적자. 동전이 HHHTHH 순서로 놓여 있다고 하자. 차례를 받은 사람은 구간을 골라야 하는데, 뒷면인 네 번째 동전이 들어간 구간은 고를 수 없다. 고른 구간이 넓을수록 뒤집는 방법이 많아지므로, 첫 번째부터 세 번째까지를 고르거나 다섯 번째부터 여섯 번째까지를 고르는 것이 의미 있는 선택이다. 첫 세 개를 골랐다면 세 동전을 뒤집는 $2^3 = 8$가지에서 아무것도 뒤집지 않는 경우를 뺀 7가지 중 하나로 뒤집어 차례를 넘긴다.

두 사람은 이 게임을 계속하는데, 지겨운 것을 싫어해서 게임을 시작할 때마다 처음 배열을 무작위로 고른다. 즉 가능한 $2^N$가지 배열 중 하나를 같은 확률로 고른다.

동전을 한 번 뒷면으로 뒤집으면 다시 앞면으로 되돌릴 방법이 없고 자기 차례에 반드시 한 개 이상을 뒤집어야 하므로, 두 사람이 최선을 다하면 승패는 반드시 갈린다. 두 사람이 최선을 다할 때, 그가 이기는 처음 배열은 몇 가지인가?

첫째 줄에 동전의 수를 나타내는 자연수 $N$ ($1 \le N \le 250$)이 주어진다.

그가 이기는 처음 배열의 개수를 출력한다. 이 수가 매우 커질 수 있으므로 1,000,000,007로 나눈 나머지를 출력한다.