100525 : 过河
描述

n块等距的石头可以踩着过河,小明的弹跳力允许他每次最多前进3块石头,求小明过河的方案数。1 2 3 和 3 2 1 不是同种方案。

输入

一行,一个正整数表示n

对于100%的数据:

1\le n \le 70

输出

一行,一个正整数表示方案数。

样例

输入

4

输出

7

输入

7

输出

44
语言:
主题: