斐波那契数列(递归)

用递归方法输出斐波那契数列第n（从0开始）项

f(0) = 0； 

f(1) = 1； 

f(n) = f(n - 1) + f(n - 2); (n>=3)

Input

一个整数n (0≤n≤30).

Output

题目中描述的 F(n)

Examples

Input

0

Output

0

Input

3

Output

2

来源

lema
Time limit 1 second
Memory limit 128 MB
讨论 统计