#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int MOD=1000000007;
long long int fie[28][3][200007]={{{0}}};
int giri[19]={0};
int hen(char a){
    if(a<='9')return a-'0';
    else return a-'A'+10;

}
int main(){
    string N;
    cin>>N;
    int K;
    cin>>K;
    int s=hen(N[0]);
    fie[1][1][0]=1;
    fie[1][0][0]=s-1;
    fie[0][0][0]=1;
    giri[s]=1;







/*

        for(int k=0;k<7;k++){
        for(int i=0;i<17;i++){
            for(int j=0;j<2;j++){
                printf("[%d]",fie[i][j][k]);
            }
            puts("");
        }
        puts("==============");
    }





*/





    for(int k=0;k<N.size()-1;k++){


                        int flg=1;

                        //for(int l=0;l<=k;l++){
                            //if(N[l]==N[k+1])flg=0;
                            if(giri[hen(N[k+1])]==1)flg=0;
                        //}




        if(k!=N.size()-1){
            giri[hen(N[k+1])]=1;
        }







        int girisyu=0;
        for(int i=0;i<16;i++){
            if(giri[i]==1)girisyu++;
        }


                        int giriikasyu=0;
                        for(int l=hen(N[k+1])-1;0<=l;l--){
                            if(giri[l]==1)giriikasyu++;
                        }





        for(int i=0;i<=16;i++){
            for(int j=0;j<2;j++){
                if(i!=0){
                    if(j==0){
                        fie[i][j][k+1]+=fie[i][j][k]*i;
                        fie[i][j][k+1]%=MOD;
                        fie[i+1][j][k+1]+=fie[i][j][k]*(16-i);
                        fie[i+1][j][k+1]%=MOD;
                    }
                    else if(j==1){


                        fie[i][0][k+1]+=fie[i][j][k]*giriikasyu;
                        fie[i][0][k+1]%=MOD;
                        fie[i+1][0][k+1]+=fie[i][j][k]*((hen(N[k+1]))-giriikasyu);
                        fie[i+1][0][k+1]%=MOD;


                        if(flg==1){
                            fie[i+1][j][k+1]+=fie[i][j][k];
                            fie[i+1][j][k+1]%=MOD;
                        }
                        else{
                            fie[i][j][k+1]+=fie[i][j][k];
                            fie[i][j][k+1]%=MOD;
                        }
                    }
                }
                else if(i==0&&j==0){
                    fie[i][j][k+1]=1;
                    fie[i][j][k+1]%=MOD;
                    fie[i+1][j][k+1]+=fie[i][j][k]*15;
                    fie[i+1][j][k+1]%=MOD;

                }
            }
        }
    }

    long long int ans=0;
    int pa=N.size()-1;
    for(int i=K;i<=K;i++){
        for(int j=0;j<2;j++){
            ans+=fie[i][j][pa];
            ans%=MOD;
        }
    }
    cout<<ans<<endl;

/*

    for(int k=0;k<7;k++){
        for(int i=0;i<17;i++){
            for(int j=0;j<2;j++){
                printf("[%d]",fie[i][j][k]);
            }
            puts("");
        }
        puts("==============");
    }

*/
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
typedef long long ll;
string num;
int rn[200005];
int k;
int n;
int dp[200005][20];
ll dfs(int x,ll now,bool zero,bool flag)
{
    int cnt=0;
    for(int i=0;i<16;i++)
    {
        if(now&(1<<i))cnt++;
    }
    if(x>=n)return cnt==k;
    if(cnt>k)return 0;
    if(!flag&&zero&&dp[x][cnt]!=-1)return dp[x][cnt];
    ll ans=0;
    int lim=flag?rn[x]:15;
    for(int i=0;i<=lim;i++)
    {
        int tmp;
        if(!zero&&i==0)tmp=now;
        else tmp=now|(1<<i);
        ans+=dfs(x+1,tmp,zero||(i!=0),flag&&(i==lim));
        ans%=mod;
    }
    if(!flag&&zero)dp[x][cnt]=ans;
    return ans;
}
int main()
{
    cin>>num>>k;
    n=num.size();
    memset(dp,-1,sizeof dp);
    for(int i=0;i<n;i++)
    {
        if(num[i]>='0'&&num[i]<='9')rn[i]=num[i]-'0';
        else rn[i]=num[i]-'A'+10;
    }
    printf("%lld\n",dfs(0,0,0,1));
    return 0;
}
