14242번 - 아름다운 그래프

정수 N이 주어진다.

완전 그래프는 모든 정점의 쌍 사이에 무방향 간선이 하나 있는 그래프를 말한다.

다음과 같이 두 조건을 만족하는 그래프를 아름답다고 한다.

• N개의 정점으로 이루어진 완전 그래프이다.
• 모든 간선에는 1 또는 2의 비용이 할당되어 있다.

즉, 아름다운 그래프는 총 2^(N*(N-1)/2) 개가 존재한다.

아름다운 그래프의 최소 스패닝 트리(MST)는 다음과 같은 조건을 만족하는 서브 그래프이다.

• N개의 정점으로 이루어진 서브 그래프이다.
• 서브 그래프는 연결되어 있다. (MST의 모든 정점 사이에 경로가 존재한다)
• 서브 그래프의 간선의 비용의 합이 최소가 되어야 한다.

한 아름다운 그래프는 여러 개의 MST를 가질 수 있다. (하지만 비용은 모두 같아야 한다)

MST는 모든 정점의 차수가 최대 2일 때, 라인이라고 한다.

f(G)를 아름다운 그래프 G의 MST 중에서 라인인 것의 개수라고 한다.

모든 아름다운 그래프의 f(G)를 합친 값을 1,000,000,007로 나눈 나머지를 출력한다.

첫째 줄에 N (2 ≤ N ≤ 16)이 주어진다.

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