Q11069: A Graph Problem 

給一個有 n ( 1 <= n <= 76 )個節點的無向圖形（圖形如下）：

你的任務是：給你 n ，請算出這個圖形有以下性質的節點子集合共有多少個。

• 集合裡不能有兩個相鄰的點。例如圖形中有n=3個節點，則集合 {1,2} 是違法的，而集合 {1,3} 是合法的。
• 當這個集合能再加入任一節點，卻可以不和其它節點相鄰，則這個集合是違法的。例如圖形中有n=5個節點，則集合 {1,5} 是違法的，因為這個集合再加入節點3仍不和其它節點相鄰，而集合 {1,3,5} 則是合法的。

所以，當圖形有 n=5 個節點時，應該有 4 個合法的集合：{1,3,5},{2,4},{2,5},{1,4}.

Input

測試資料中有很多個測資，每個測資一列，每列包含一個數字 n，1 <= n <= 76。請用EOF來判斷檔案結束。

Output

請輸出一列 含有上述性質的子集合的數目。你可以假設答案不會超過 2³¹。

Sample Input

1
2
3
4
5
30

Sample Output

1
2
2
3
4
4410

translated by TimeString