C1-Zexal的过河

题目描述

$Zexal$打算借助河中间的石砖过到河对岸去。$Zexal$从第一块石砖出发，接下来他可以走到第二块石砖或第三块石砖，有时候走的很不爽，甚至可以直接跨过两个石砖，到达第四块石砖，但是不能连续两次这种操作，因为这样消耗体能比较大。现在假设河中含$n$块石砖，且这些石砖呈直线分布，请你计算出Zexal从第一块石砖出发有多少种安全的过河方法。

输入

输入将由多组测试数据组成，以EOF结尾。

每组数据只有一行，为河中的总石砖数$n（0＜n≤50）$。

输出

对于每组数据，输出一行，为过河的方法数。

输入样例

1
2
3

输出样例

1
2
4

样例解释

1：一步走完；
2：先走到2再走完，或者直接走完；
3：111或12或21或3。