题目描述

荣荣是一只快乐的小青蛙，每天坐在井里看太阳。有一天下大雨，从她以往的经验来看，这口井很快就会被淹没，因此她必须依靠井边的梯子跳出去。她每次可以跳两格梯子，也可以跳三格梯子。请你帮她想想，她有多少种方案可以跳出这口井？

输入格式

输入数据只有一行，包含一个整数 $n$（$1 \le n \le 50$），表示梯子的格数。

输出格式

输出一行，表示荣荣跳出这口井的不同的方案数。

样例

1

1

3

2

说明

如果当前无论跳 $2$ 格还是跳 $3$ 格都能跳出这口井，则这两种跳法算作 $1$ 种方案。

当荣荣跳到第 $n$ 格， 或超过第 $n$ 格视为跳出了这口井。