Network

Time limit2sMemory limit128 MB

Summary

Count non-isomorphic trees on N+1 nodes where one fixed hub node has any degree but every other node must have odd degree.

Level: Hard8 of 10
Topics: Combinatorics, Tree, Math, Dynamic programming
Solved: No attempts yet

Problem

An academy wants to connect the students' computers and one assistant's computer into one network.

There are N students today. All N student computers and the assistant's computer must be connected. The connections must not contain a cycle. Each student computer must be directly connected to an odd number of other computers. There is no restriction on the degree of the assistant's computer. When there are 5 students, possible connection patterns include the following.

       S               S     S              S          S  S 
       |                \    |              |          | /   
   S---C----S            C---S          C---S      C---S    
       | \              /    |              |          | \  
       S  S            S     S          S---S---S      S  S

For two graphs G and G', if G' can be obtained from G only by moving the drawing around without changing adjacencies, the two graphs are considered the same. In other words, if the pattern relative to the assistant's computer is the same, the graphs are the same. Drawings can look different while representing the same graph. The following two drawings represent the same graph.

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

Given N, compute the number of different networks.

Input

The first line contains the number of students N. N is a positive integer not greater than 40.

Output

Print the number of different networks.

Examples3

Example 1
Input
```
5
```
Expected output
```
4
```
Example 2
Input
```
1
```
Expected output
```
1
```
Example 3
Input
```
40
```
Expected output
```
929556155
```