#include<bits/stdc++.h>
const int N=200010,mod=1e9+7;
char s[N];
int c[N],fac[N],f[17][N],n,KK,a[17],cnt,g[N][17],C[17][17];
int qp(int x,int y)
{
	int ans=1;
	for(;y;y >>=1,x=1ll*x*x%mod)
		if(y&1)ans=1ll*ans*x%mod;
	return ans;
}
void ins(int x)
{
	if(!a[x]++)cnt++;
}
void eras(int x)
{
	if(!--a[x])
		cnt--;
}	
int main()
{
	scanf("%s",s+1),n=strlen(s+1);
	scanf("%d",&KK);
	for(int i=0;i<=16;i++)
		C[i][0]=C[i][i]=1;
	for(int i=1;i<=16;i++)
		for(int j=1;j<i;j++)
			C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
	for(int i=fac[0]=1;i<=16;i++)
		fac[i]=1ll*fac[i-1]*i%mod;
	g[0][0]=1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=i&&j<=16;j++)
			g[i][j]=(1ll*j*g[i-1][j]+g[i-1][j-1])%mod;
	
	f[KK][n+1]=1;
	for(int j=0;j<=KK;j++)
		for(int i=n;i;i--)
			for(int k=0;k<=j;k++)
				f[j][i]=(f[j][i]+1ll*C[16-j][KK-j]*C[j][k]%mod*g[n-i+1][KK-j+k]%mod*fac[KK-j+k])%mod;
	for(int i=1;i<=n;i++)
		c[i]=(isdigit(s[i])?s[i]-'0':s[i]-'A'+10);
	int ans=0;
	for(int i=1;i<=n;ins(c[i++]))
		for(int j=i==1;j<=c[i]-(i!=n);j++)
			ins(j),ans=(ans+f[cnt][i+1])%mod,eras(j);
	for(int i=2;i<=n;i++)ans=(ans+1ll*f[1][i+1]*15)%mod;
	printf("%d\n",ans);
	return 0;
}
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+50;
const int mod=1e9+7;
char s[N];
int k;
int dig[N];
// 低i位满足有k个不同数位的数字个数
ll dp[N][22];
void print(int x){
    if(x){
        print(x/2);
    }
    printf("%d",x%2);
}
ll dfs(int idx,int sta,int dif,bool lead,bool limit){
    if(idx==-1){
        // 一个合法数字(这题要排除含前导零的数)，有时候要单独考虑0的情况
        // 其实我觉得前导零的命名有点误导性，其实lead为true就是表示现在搜索的前缀是一串0
        if(dif==k && !lead){
            return 1;
        }else{
            return 0;
        }
    }
    // 记忆化的都是无上限的
    if(!limit && dp[idx][dif]!=-1){
        return dp[idx][dif];
    }
    // 这一位的枚举上限
    int up=limit?dig[idx]:15;
    ll ans=0;
    for(int i=0;i<=up;i++){
        if(lead && i==0 || (sta>>i)&1){
            ans+=dfs(idx-1,sta,dif,lead && i==0,limit && i==up);
        }else{
            ans+=dfs(idx-1,sta|(1<<i),dif+1,lead && i==0,limit && i==up);
        }
        ans%=mod;
    }
    if(!limit){
        dp[idx][dif]=ans%mod;
    }
    return ans%mod;
}
int main(){
    scanf("%s %d",s,&k);
    int n=strlen(s);
    for(int i=n-1;i>=0;i--){
        if(s[i]>='A'){
            dig[n-1-i]=s[i]-'A'+10;
        }else{
            dig[n-1-i]=s[i]-'0';
        }
    }
    memset(dp,-1,sizeof(dp));
    // 从高位搜索下去
    ll ans=dfs(n-1,0,0,true,true);
    printf("%lld\n",ans%mod);
    return 0;
}