시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 13 0 0 0.000%

문제

2008년 4월 9일 수요일은 대한민국의 제 18대 국회의원 선거이기도 하지만, 모의고사를 보는 날이다.

이미 Marking 2.0이란 채점프로그램을 만든 사람은 이번 모의고사를 위해 Marking 2.0을 인터넷 버전으로 수정했다. Marking 2.0의 인터넷 버전은 이미 우리가 예전에 보던 PKU나 UVA와 비슷한 온라인 채점 사이트이다.

하지만, 학생들이 인터넷을 이용해서 딴짓을 할 가능성이 있기 때문에, 내부 그래프를 이용하려고 한다. 따라서, 조교는 랜선을 이용해서 서로의 노트북을 연결하려고 한다.

현재 학생은 총 N명이 있다. N명의 학생과 1명의 조교를 랜선으로 연결하려고 한다. 단 이 때, 사이클을 형성하면 안된다. 그리고, 모든 학생들의 컴퓨터에는 반드시 홀수개의 랜선이 달려야 한다.

학생의 수가 주어졌을 때, 가능한 그래프의 경우를 구하는 프로그램을 작성하시오.

5명의 학생일 때는, 다음과 같은 그래프가 존재한다.

다음의 그림에서 C는 조교, S는 학생, 그리고 나머지는 각각의 랜선이 어떻게 연결되어있는지를 나타낸다.

만약, 두 개의 그래프 G와 G' 이 있을 때, G의 연결을 고치지 않고, 단지 변형을 통해 G'을 만들 수 있을 때, G와 G'은 같은 그래프이다.

다시말해서, 조교를 기준으로 같은 패턴으로 연결이 되어 있으면, 그것은 같은 그래프이다.

그림으로 그렸을 때는, 다른 모양이 나오더라도, 같은 그래프일 수 는 있다.

예를 들어 다음 그래프는 서로 같다.

학생의 수 N이 주어졌을 때, 서로 다른 그래프의 경우의 수중 서로 다른 것의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 학생의 수 N이 주어진다. N은 40보다 작거나 같은 자연수이다.

출력

첫째 줄에 경우의 수를 출력한다.

예제 입력

5

예제 출력

4

힌트

출처