算法题：UVa 11069 A Graph Problem （斐波那契）

算法题：UVa 11069 A Graph Problem （斐波那契）2014-04-19A Graph Problem

Time limit: 2s

Given an undirected graph of the following form with n nodes, 1 ≤ n ≤ 76:

Your task is to calculate the number of subsets of nodes of the graph with the following properties:

no nodes in the subset should be connected

it shouldn"t be possible to add further nodes to the subset without violating the first condition

For a graph with 5 nodes the number of 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

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

Sample input

Sample output

4410