Rooted Trees Problem

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/32768 K (Java/Others)

Description

Give you two definitions tree and rooted tree. An undirected connected graph without cycles is called a tree. A tree is called rooted if it has a distinguished vertex r called the root. Your task is to make a program to calculate the number of rooted trees with n vertices denoted as Tn. The case n=5 is shown in Fig. 1.

Input

There are multiple cases in this problem and ended by the EOF. In each case, there is only one integer means n(1<=n<=40) .

Output

For each test case, there is only one integer means Tn.

Sample Input

1 2 5

Sample Output

1 1 9

Hint

lcy

Source

杭电ACM集训队训练赛(VIII)

提交代码