아름다운 그래프

정수 $N$이 주어진다.

완전 그래프는 서로 다른 두 정점마다 무방향 간선이 정확히 하나씩 있는 그래프다.

다음 두 조건을 만족하는 그래프를 아름다운 그래프라고 한다.

• 정점이 $N$개인 완전 그래프다.
• 모든 간선의 비용이 $1$ 또는 $2$다.

따라서 아름다운 그래프는 모두 $2^{N(N-1)/2}$개다.

아름다운 그래프 $G$의 최소 스패닝 트리(MST)는 다음 조건을 만족하는 부분 그래프다.

• $G$의 정점 $N$개를 모두 포함한다.
• 연결되어 있다. 즉 어떤 두 정점 사이에도 경로가 있다.
• 간선 비용의 합이 최소다.

한 아름다운 그래프의 MST는 여러 개일 수 있다. 이때 비용은 모두 같다.

MST의 모든 정점의 차수가 $2$ 이하이면 그 MST를 라인이라고 한다.

$f(G)$는 아름다운 그래프 $G$의 MST 중 라인인 것의 개수다.

정점이 $N$개인 모든 아름다운 그래프 $G$에 대해 $f(G)$를 더한 값을 1,000,000,007로 나눈 나머지를 출력한다.

첫째 줄에 $N$이 주어진다. ($2 \le N \le 16$)

첫째 줄에 정답을 출력한다.