题目详情 - Thenumberofmaximumsubset

ID: 1159

远端评测题

1000ms

128MiB

难度: (无)

上传者:

You are given a set with n distinct numbers of 1 to n, and your task is to calculate the number of maximum subsets with the following properties:

no two elements in the subset should be adjacent

it shouldn't be possible to add numbers to the subset without violating the first condition

For example, if n = 5, the number of maximum subsets which fulfill the above conditions is 4. The subsets are {1,3,5},{2,4},{2,5},{1,4}.

Input

The input will consist of a sequence of numbers n,1 ≤ n ≤ 76. Each number will be on a separate line. The input will be terminated by EOF.

Output the number of maximum subsets as described above on a single line. The number of all subsets will be less than 2^31.