map<ll,ll>src,dst;
ll@n,@s;
src[s]=1;
rep(n){
	ll@a;
	for(auto t:src){
		for(ll b=a;t.first-b>=0;b*=a){
			dst[t.first-b]+=t.second;
		}
	}
	swap(src,dst);
	dst.clear();
}
ll z=0;
for(auto t:src){
	z+=t.second;
}
wt(z);