Dragonfly got a lot of n chocolates someday. However, he had caught up with toothache in the recent days and was therefore reluctant to

distribute those chocolates among his friends. Anyhow, he had so a large group of friends. Dragonfly thus ranked them in orders from 1 to m
in line with their distinct intimacy rates and he determined to distribute the chocolates according to the following principles:
I. Suppose friend ranked with i got x chocolates. Then friend ranked with i+1 should got chocolates no more than x+k chocolates
and no less than x chocolates where k is a positive integer.
II. No.1 friend should get no more than k chocolates.
III. It is even possible for some friends to get no chocolates.
IV. If possible, all chocolates should be distributed and none were left.
Although Dragonfly is not good at mathematics, he is eager to know the number of ways that all chocolates could be distributed
and he ask to you to help him.

输入格式

Input file consists of a series of input lines each defining one case. Input for each case is a single line of three positive integers:

n(1 <= n <= 500), m (1 <= m <= 100), k (1 <= k <= 100).
Input file will be terminated by 0 0 0.

输出格式

For each case output the number of ways that all chocolates could be distributed on a single line.

样例输入

1 1 1
4 2 2
5 3 2
0 0 0

样例输出

1
2
3

#include<stdio.h> 
#include<string.h>
int i,j,u,n,m,k;
int f[501][101][31];
void sum(){
 	int p;
    int q=f[i][j][0]>=f[i-u*j][j-1][0]?f[i][j][0]:f[i-u*j][j-1][0];
 	for(p=1;p<=q;p++)
 		f[i][j][p]+=f[i-u*j][j-1][p];
    if(q==f[i-u*j][j-1][0])  
    	f[i][j][0]=q;
    for(q=1;q<=f[i][j][0];q++)
    if(f[i][j][q]>9){
        f[i][j][q+1]+=f[i][j][q]/10;
        f[i][j][q]=f[i][j][q]%10;
    }
    if(f[i][j][q]!=0&&q>f[i][j][0])
        f[i][j][0]=q;
}
int main(){
    int t; 
    while(1){
        scanf("%d %d %d",&n,&m,&k);
        if(n==0&&m==0&&k==0)
			break;
        memset(f,0,sizeof(f));
        f[0][0][0]=1;
        f[0][0][1]=1;
        for(i=0;i<=n;i++)
        for(j=1;j<=m;j++){
   	    	f[i][j][0]=1;
            for(u=0;u<=k;u++)
 	        if(i-u*j>=0)
            sum();
        }
        for(t=f[n][m][0];t>=1;t--)
        	printf("%d",f[n][m][t]);
        printf("\n");
    }
    return 0;
}