取石子

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

X虽然很爱学习,但也有贪玩的时候。现在有N个石子,X每次可以取一个,两个,或三个。问一共有多少种不同的方法可以将这些石子取完。
对于两种不同的方法的定义:两种方法取得次数不一样,或者在第i次时取得数目不一样。

Input

多组输入。

每组输入一个整数N(N <=35),代表一共有N个石子。

Output

对于每组输入,输出一个整数,代表有多少种方案。

Sample Input

1
2
35

Sample Output

1
2
1132436852

Hint

Source

zmx