#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
typedef long long ll;
ll read(){
ll t=,f=;char ch=getchar();
while (ch<''||ch>''){if (ch=='-')f=-;ch=getchar();}
while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}
return t*f;
} int n,K,lim,ans=;
int a[],tot=,cnt[],C[][];
ll pw_[],*pw; void dp(int id,bool f,bool f2) {
if (id==) {
++ans;
return;
}
if (f2) {
for (int i=;i<=(f?:a[id]);i++)
if (cnt[i]>) {
--cnt[i];
dp(id-,f|(i<a[id]),);
++cnt[i];
}
return;
}
if (f) {
int tmp=;
for (int j=;j<=;j++)
tmp*=C[id][cnt[j]],
id-=cnt[j];
ans+=tmp;
return;
}
for (int i=;i<=a[id];i++)
if (cnt[i]>) {
--cnt[i];
dp(id-,f|(i<a[id]),);
++cnt[i];
}
}
void dfs(int num,int tot2,int used){
if (num==){
cnt[]=tot2-used;
int p=-,g=;
for (int i=;i<=&&p==-;g+=cnt[i++]){
if (g<(tot2+)/&&g+cnt[i]>=(tot2+)/)
p=i;
}
ll val=;
for (int i=;i<=;i++)
val+=cnt[i]*pw[i-p];
if (val<=lim) dp(tot2,tot2<tot,);
return;
}
for (int i=;i<=tot2-used;i++){
cnt[num]=i;
dfs(num+,tot2,used+i);
}
}
void init(){
pw=pw_+;
for (int i=-;i<=;i++){
pw[i]=;
for (int j=;j<=K;j++)
pw[i]*=i;
}
C[][]=;
for (int i=;i<=;i++){
C[i][]=;
for (int j=;j<=i;j++)
C[i][j]=C[i-][j]+C[i-][j-];
}
}
int main(){
n=read();K=read();lim=read();init();
while (n){
a[++tot]=n%;
n/=;
}
for (int i=;i<=tot;i++) dfs(,i,);
printf("%d\n",ans);
}