#include<stdio.h>
long long int power_l(int x,int y,int limit){
	int i;
	long long int ans=1;
	for(i=0;i<y;i++){
		ans*=x;
		if(ans>limit){
			return -1;
		}
	}
	return ans;
}

int gcd(int x,int y){
	int r=x%y;
	while(r!=0){
		x=y;
		y=r;
		r=x%y;
	}
	return y;
}
		

int dp(int p,int q,int k,int l,int m){
	if(m<=0||l<=0||k<=0){
		return 0;
	}
	if(p==1 && q<=l && q<=k && m==1){
		return 1;
	}
	int ans=0;
	int gcd_num;
	int i;
	long long int pow;
	ans+=dp(p,q,k-1,l,m);
	for(i=1;i<=7;i++){
		if(k*p-i*q<0||k*q<=0){
			continue;
		}
		pow=power_l(k,i,l);
		if(pow==-1){
			continue;
		}
		if(k*p-i*q==0){
			if(m-i>=0){
				ans++;
			}
			continue;
		}
		gcd_num=gcd(k*p-i*q,k*q);
		ans+=dp( (k*p-i*q)/gcd_num,k*q/gcd_num,k-1,l/pow,m-i);
	}
	return ans;
}

int main (){
	int p,q,a,n;
	int x;
	scanf("%d %d %d %d",&p,&q,&a,&n);
	while(!(p==0&&q==0&&a==a&&n==0)){
		x=a<800?a:800;
		printf("%d\n",dp(p,q,x,a,n));
		scanf("%d %d %d %d",&p,&q,&a,&n);
	}
	return 0;
}