시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB416545.455%

문제

2008년 4월 9일 수요일은 대한민국의 제 18대 국회의원 선거이기도 하지만, 모의고사를 보는 날이다. 최백준 조교는 Marking 2.0이라는 채점프로그램을 만들었고, 이를 바탕으로 웹사이트를 하나 만들었다. 이 웹사이트를 테스트하기 위해 학원 내에서 서로의 컴퓨터를 연결해보려고 한다.

오늘 학원에는 학생이 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'을 만들 수 있으면, G와 G'은 같은 그래프이다. 즉, 최백준 조교를 기준으로 같은 패턴으로 연결이 되어 있으면, 그것은 같은 그래프이다. 그림으로 그렸을 때는 다른 모양이 나오더라도, 같은 그래프일 수 는 있다. 예를 들어, 다음 두 그래프는 같다.

   S   S   S          S       S                                      
   |   |   |          |       |  
   S---C---S      S---C-------S                                                 
   |   |   |          |       | 
   S   S   S      S---S---S   S          

학생의 수 N이 주어졌을 때, 서로 다른 그래프의 경우의 수를 구해보자.

입력

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

출력

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

예제 입력 1

5

예제 출력 1

4

예제 입력 2

1

예제 출력 2

1

예제 입력 3

40

예제 출력 3

929556155

출처