Subset

Time Limit: 1000 mSec

Memory Limit: 32768 KB

Description

整数集合Sn={1,2,...,n}的非空子集如果不含两个相邻的自然数,则称为好子集。你的任务是求好子集的个数。

Input

有多组测试数据。每个测试数据一行,有一个正整数,表示n(1≤n≤70)。

Output

对于每组测试数据,输出一个数表示Sn的好子集的个数

Sample Input

3

Sample Output

4

Hint

{1},{2},{3},{1,3}.

Source

FOJ月赛-2007年9月

提交代码