4071 - 基础算法-递推算法:取数问题

通过次数

34

提交次数

92

Time Limit : 1 秒
Memory Limit : 128 MB

我们来玩一个游戏:自然数1到N,按顺序列成一排,你可以从中取走任意个数,但是相邻的两个不可以同时被取走,求一共有多少种取法。

Input

输入一个数字,表示一共有几个数字,数字小于100

Output

输出一个数字,表示有多少种取法?

Examples

Input

1

Output

2

Input

2

Output

3