1 #include<cstdio>
2 #include<iostream>
3 #include<cmath>
4 #include<cstring>
5 #include<algorithm>
6 typedef long long ll;
7 ll read(){
8 ll t=0,f=1;char ch=getchar();
9 while (ch<'0'||ch>'9'){if (ch=='-')f=-1;ch=getchar();}
10 while ('0'<=ch&&ch<='9'){t=t*10+ch-'0';ch=getchar();}
11 return t*f;
12 }
13
14 int n,K,lim,ans=0;
15 int a[20],tot=0,cnt[10],C[15][15];
16 ll pw_[30],*pw;
17
18 void dp(int id,bool f,bool f2) {
19 if (id==0) {
20 ++ans;
21 return;
22 }
23 if (f2) {
24 for (int i=1;i<=(f?9:a[id]);i++)
25 if (cnt[i]>0) {
26 --cnt[i];
27 dp(id-1,f|(i<a[id]),0);
28 ++cnt[i];
29 }
30 return;
31 }
32 if (f) {
33 int tmp=1;
34 for (int j=0;j<=9;j++)
35 tmp*=C[id][cnt[j]],
36 id-=cnt[j];
37 ans+=tmp;
38 return;
39 }
40 for (int i=0;i<=a[id];i++)
41 if (cnt[i]>0) {
42 --cnt[i];
43 dp(id-1,f|(i<a[id]),0);
44 ++cnt[i];
45 }
46 }
47 void dfs(int num,int tot2,int used){
48 if (num==9){
49 cnt[9]=tot2-used;
50 int p=-1,g=0;
51 for (int i=0;i<=9&&p==-1;g+=cnt[i++]){
52 if (g<(tot2+1)/2&&g+cnt[i]>=(tot2+1)/2)
53 p=i;
54 }
55 ll val=0;
56 for (int i=0;i<=9;i++)
57 val+=cnt[i]*pw[i-p];
58 if (val<=lim) dp(tot2,tot2<tot,1);
59 return;
60 }
61 for (int i=0;i<=tot2-used;i++){
62 cnt[num]=i;
63 dfs(num+1,tot2,used+i);
64 }
65 }
66 void init(){
67 pw=pw_+12;
68 for (int i=-9;i<=9;i++){
69 pw[i]=1;
70 for (int j=1;j<=K;j++)
71 pw[i]*=i;
72 }
73 C[0][0]=1;
74 for (int i=1;i<=12;i++){
75 C[i][0]=1;
76 for (int j=1;j<=i;j++)
77 C[i][j]=C[i-1][j]+C[i-1][j-1];
78 }
79 }
80 int main(){
81 n=read();K=read();lim=read();init();
82 while (n){
83 a[++tot]=n%10;
84 n/=10;
85 }
86 for (int i=1;i<=tot;i++) dfs(0,i,0);
87 printf("%d
",ans);
88 }
