思路：模拟

有$n$枚硬币，每次可以取1枚或者取2枚，求取完$n$枚硬币有多少种取法。

考虑将取$n$枚硬币的问题(假设为$f(n)$)分解子问题，当我们取到$n$枚硬币时，上一次可以是取一枚硬币，那么其方法数为$f(n-1)$；也可以是取两枚硬币，那么其方法数为$f(n-2)$。

那么就有$f(n)=f(n-1)+f(n-2)$的递推式。

题目描述

在移动支付尚未流行的年代，塔子哥是一个狂热的硬币收藏家。

他喜欢收集各种各样的硬币，将其存放进自己的储蓄罐中。当储蓄罐满了，他就得破开储蓄罐，并将所有硬币放入一个更大的储蓄罐中。久而久之，他的储蓄罐越来越大。

这天，他又得转移硬币了，但是他每次只能转移一枚或者两枚硬币。

已知塔子哥有$n$枚硬币，他能够有多少种转移方法？

输入描述

一个正整数$n(1{\leq}n\leq50)$，代表硬币的数量。

输出描述

一个正整数，代表一共有多少转移方法。

示例1

输入

3

输出

3