BL always like to play a game called Greeeeedy.Firstly he get a number ,then he should divide the number using plus.But Greeeeedy game requal that the number exits in the formula be not larger than 3.For exemple:as get 5,then he can divide 4 like as

BL always like to play a game called Greeeeedy.Firstly he get a number ,then he should divide the number using plus.But Greeeeedy game requal that the number exits in the formula be not larger than 3.For exemple:as get 5,then he can divide 4 like as
BL always like to play a game called Greeeeedy.Firstly he get a number ,then he should divide the number using plus.But Greeeeedy game requal that the number exits in the formula be not larger than 3.
For exemple:as get 5,then he can divide 4 like as the following methods:
3+2 2+3 1+2+2 2+1+2 2+2+1 1+1+1+2 2+1+1+1 ….(be careful that 1+2+2 is different from 2+1+2)
And 4+1 is not allowable.
Now BL is curious about how many different methods he can use when he get a number,could you help him?
Input
The input consists of mutiply cases.each line contains one integer N (0 < N < 50),the test will be ended when N=0;
Output
For each test case,output one line containa a integer represent the number of different divide methed.
Sample Input
3
4
0
Sample Output
4
7
Hint
for 3,there are 4 methods :
1+1+1
2+1
1+2
3
Becareful that as the N become larger,a[N] will be too large
是不是a[1]=1;a[2]=2;a[3]=4;
a[i]=a[i-1]+a[i-2]+i-3; (i>=4);

BL always like to play a game called Greeeeedy.Firstly he get a number ,then he should divide the number using plus.But Greeeeedy game requal that the number exits in the formula be not larger than 3.For exemple:as get 5,then he can divide 4 like as
递推公式我可以给你,是绝对没问题的.
你看任何一条表达式末尾一定是+1或者+2或者+3；
根据这个原理你很快就得到
a[n]=a[n-1]+a[n-2]+a[n-3];
其中a[1]=1;a[2]=2;a[3]=4;
我知道了,原因是当n=36之后,a[n]已经超出double了.
#include
#include
int a[50][50];
void caln(){
int i,j,f;
memset(a,0,sizeof(a));
a[0][0]=1;
a[0][1]=1;
a[1][0]=1;
a[1][1]=2;
a[2][0]=1;
a[2][1]=4;
for(i=3;i