一格与三格砖

题目描述

用长度 1 和长度 3 的砖拼满长度 n 的一行。砖没有颜色区别，同长度砖不可区分，先后长度序列不同算不同方案，不重叠也不留空。n=0 有一种空方案。

输入格式

输入 n。

输出格式

输出方案数。

样例 1

输入

4

输出

3

说明

砖长序列为 1111、13、31。

样例 2

输入

2

输出

1

说明

只能用两块一格砖。

数据范围

• 0≤n≤40；答案使用 long long。