Problem2811--搬砖头 [rock](1)

2811: 搬砖头 [rock](1)

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 0  Solved: 0
[Status] [Submit] [Creator:]

Description

小可可一直对中国五千年的古老文明非常感兴趣,学习历史知识之余,他报名参加了少年考古队,跟随正式的考古队进行考古发掘,通过实践来更好的领会书本知识。这次考古队发现了一个非常巨大的古墓,具有非常高的考古价值,小可可随队来到了考古现场。经过紧张的发掘,古墓的墓道终于显露出来,但是它被一块块方砖封住了,现在小可可的任务就是帮助考古队将这些方砖移走,打通墓道。由于这些保存完好的古代方砖也是珍贵的文物,所以规定一次最多只能搬三块砖。小可可在搬砖的过程中一直在思考一个问题,他很想知道将这些砖头搬走共有多少种不同的搬法。
例如,现在总共有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次搬完,第一次搬三个,第二次搬一个)
你能不能帮助小可可解决这个问题呢?



Input

共一行。是一个1~1000的正整数N,表示共有N块砖头。



Output

共一行。输出一个正整数表示N块砖头移动的方法数。

Sample Input Copy

4

Sample Output Copy

7

Source/Category