提示: 欢迎访问OurACM平台。
Problem 1533 Subset

Accept: 298    Submit: 729
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem 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月

Submit  Back  Status  Discuss