네트워크
시간 제한2초메모리 제한128 MB
N+1개의 노드로 된 트리 중 허브 노드 하나는 차수가 자유롭고 나머지 노드는 모두 홀수 차수를 갖는 비동형 트리의 개수를 구합니다.
문제
어느 학원에서 학생들의 컴퓨터와 조교의 컴퓨터를 연결해 하나의 네트워크를 만들려고 한다.
오늘 학원에는 학생이 N명 있다. N명의 학생 컴퓨터와 조교 컴퓨터 1대를 모두 연결해야 한다. 연결 전체에는 사이클이 없어야 한다. 또한 각 학생의 컴퓨터는 다른 컴퓨터와 홀수 개만큼 직접 연결되어 있어야 한다. 조교의 컴퓨터에 연결된 개수에는 제한이 없다. 학생이 5명인 경우 가능한 연결 모양에는 다음과 같은 것들이 있다.
S S S S S S
| \ | | | /
S---C----S C---S C---S C---S
| \ / | | | \
S S S S S---S---S S S
두 그래프 G와 G'가 있을 때, G의 연결 관계를 바꾸지 않고 그림에서 위치만 변형해 G'를 만들 수 있다면 두 그래프는 같은 그래프로 본다. 즉, 조교 컴퓨터를 기준으로 같은 패턴으로 연결되어 있으면 같은 그래프다. 그림의 모양이 달라도 같은 그래프일 수 있다. 다음 두 그림도 같은 그래프를 나타낸다.
S S S S S
| | | | |
S---C---S S---C-------S
| | | | |
S S S S---S---S S
학생 수 N이 주어질 때, 서로 다른 네트워크의 수를 구하라.
입력
첫째 줄에 학생의 수 N이 주어진다. N은 40 이하인 자연수이다.
출력
첫째 줄에 서로 다른 네트워크의 수를 출력한다.