时间限制:1000ms  空间限制:256MB

题目描述

考古队发现了一个非常巨大的古墓，具有非常高的考古价值，你随队来到了考古现场。经过紧张的发掘，古墓的墓道终于显露出来，但是它被一块块方砖封住了，现在你的任务就是帮助考古队将这些方砖移走，打通墓道。由于这些保存完好的古代方砖也是珍贵的文物，所以规定一次最多只能搬三块砖。那将这些砖头搬走共有多少种不同的搬法。

例如，现在总共有4个砖头，那么可以选择的方法有以下7种：

1，1，1，1（分4次搬完，每次搬一个砖头）

1，2，1（分3次搬完，第一次搬一个，第二次搬两个，第三次搬一个）

1，1，2（分3次搬完，第一次搬一个，第二次搬一个，第三次搬两个）

2，1，1（分3次搬完，第一次搬两个，第二次搬一个，第三次搬一个）

2，2（分2次搬完，第一次搬两个，第二次搬两个）

1，3（分2次搬完，第一次搬一个，第二次搬三个）

3，1（分2次搬完，第一次搬三个，第二次搬一个）

输入格式

一个1～40的正整数N，表示共有Ｎ块砖头。

输出格式

一个正整数,表示N块砖头移动的方法数。

样例

输入#1

4

输出#1

7