#include <bits/stdc++.h>
#define MOD 1000000007LL
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

ll fact[200005];

ll mod_pow(ll x,ll n){
	ll res=1;
	while(n>0LL){
		if(n&1LL){
			res=res*x%MOD;
		}
		x=x*x%MOD;
		n>>=1LL;
	}
	return res;
}

ll extgcd(ll a,ll b,ll& x,ll& y){
	ll d=a;
	if(b!=0LL){
		d=extgcd(b,a%b,y,x);
		y-=(a/b)*x;
	}else{
		x=1;
		y=0;
	}
	return d;
}

ll mod_inverse(ll a,ll m){
	ll x,y;
	extgcd(a,m,x,y);
	return (m+x%m)%m;
}

ll mod_fact(ll n,ll p,ll& e){
	e=0;
	if(n==0)return 1;
	ll res=mod_fact(n/p,p,e);
	e+=n/p;
	if(n/p%2!=0){
		return res*(p-fact[n%p])%p;
	}
	return res*fact[n%p]%p;
}

ll mod_comb(ll n,ll k,ll p=MOD){
	if(n<0 || k<0 || n<k)return 0;
	ll e1,e2,e3;
	ll a1=mod_fact(n,p,e1),a2=mod_fact(k,p,e2),a3=mod_fact(n-k,p,e3);
	if(e1>e2+e3)return 0;
	return a1*mod_inverse(a2*a3%p,p)%p;
}


int n;
string s;
int K;
int val[200005];
ll dp[200005][20];
int cnt[17];
ll ans;

int main(void){
	fact[0]=1;
	for(ll i=1;i<=200000;i++){
		fact[i]=fact[i-1]*i%MOD;
	}
	cin >> s >> K;
	n=s.size();
	for(int i=0;i<n;i++){
		if(s[i]>='0' && s[i]<='9'){
			val[i]=(s[i]-'0');
		}else{
			val[i]=(s[i]-'A')+10;
		}
	}
	int ct=0;
	for(int i=0;i<n;i++){
		for(int j=0;j<=15;j++){
			if(i==0 && j==0)continue;
			if(j<val[i]){
				if(cnt[j]!=0)dp[i+1][ct]++;
				else{
					dp[i+1][ct+1]++;
				}
			}
		}
		cnt[val[i]]++;
		if(cnt[val[i]]==1){
			ct++;
		}
	}
	if(ct==K){
		ans++;
	}
	for(int i=1;i<n;i++){
		dp[i][0]++;
		for(int j=0;j<=K;j++){
			if(dp[i][j]==0)continue;
			if(j==0){
				dp[i+1][1]+=dp[i][j]*15%MOD;
				dp[i+1][1]%=MOD;
			}else{
				dp[i+1][j]+=dp[i][j]*j%MOD;
				dp[i+1][j]%=MOD;
				dp[i+1][j+1]+=dp[i][j]*(16-j)%MOD;
				dp[i+1][j+1]%=MOD;
			}
		}
	}
	ans+=dp[n][K];
	ans%=MOD;
	printf("%lld\n",ans);
	return 0;
}

#include<bits/stdc++.h>
#define For(i,a,b) for(register int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(register int i=(a);i>=(b);--i)
//#define int long long
using namespace std;
inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}

#define mod 1000000007
struct modint{
    int x;
    modint(int o=0){x=o;}
    modint &operator = (int o){return x=o,*this;}
    modint &operator +=(modint o){return x=x+o.x>=mod?x+o.x-mod:x+o.x,*this;}
    modint &operator -=(modint o){return x=x-o.x<0?x-o.x+mod:x-o.x,*this;}
    modint &operator *=(modint o){return x=1ll*x*o.x%mod,*this;}
    modint &operator ^=(int b){
        modint a=*this,c=1;
        for(;b;b>>=1,a*=a)if(b&1)c*=a;
        return x=c.x,*this;
    }
    modint &operator /=(modint o){return *this *=o^=mod-2;}
    modint &operator +=(int o){return x=x+o>=mod?x+o-mod:x+o,*this;}
    modint &operator -=(int o){return x=x-o<0?x-o+mod:x-o,*this;}
    modint &operator *=(int o){return x=1ll*x*o%mod,*this;}
    modint &operator /=(int o){return *this *= ((modint(o))^=mod-2);}
    template<class I>friend modint operator +(modint a,I b){return a+=b;}
    template<class I>friend modint operator -(modint a,I b){return a-=b;}
    template<class I>friend modint operator *(modint a,I b){return a*=b;}
    template<class I>friend modint operator /(modint a,I b){return a/=b;}
    friend modint operator ^(modint a,int b){return a^=b;}
    friend bool operator ==(modint a,int b){return a.x==b;}
    friend bool operator !=(modint a,int b){return a.x!=b;}
    bool operator ! () {return !x;}
    modint operator - () {return x?mod-x:0;}
};
inline modint qpow(modint a,int b){
	return  a^b;	
}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;
#define maxn 200005
#define inf 0x3f3f3f3f
char str[maxn];
int n,d[maxn],k;
modint cnt[maxn][23];
modint fac[44],ifac[44];
inline void prework(int n){
	fac[0]=ifac[0]=1;
	For(i,1,n)fac[i]=fac[i-1]*i,ifac[i]=ifac[i-1]/i;
}
inline modint C(int n,int m){
	if(n<m||n<0||m<0)return 0;
	return fac[n]*ifac[m]*ifac[n-m];
}
int c[1<<17];
modint dfs(int now,int st,bool lim,bool zero){
	if(now==n+1) return 
	//cout<<"val "<<(c[st]==k)<<endl,
	c[st]==k;
	if(!lim && !zero) return 
	//cout<<n-now+1<<" "<<c[st]<<endl,
	cnt[n-now+1][c[st]];
	int r=lim?d[now]:15;
	modint res=0;
	For(i,0,r){
		if(i||!zero)res+=dfs(now+1,st|(1<<i),lim&&(i==r),0);
		else res+=dfs(now+1,st,lim&&(i==r),1);
	}
	return res;
}
modint pw[23][maxn];

signed main()
{
	scanf("%s",str+1);
	n=strlen(str+1);
	prework(30);
	For(i,1,n){
		if(isdigit(str[i]))d[i]=str[i]-'0';
		else d[i]=str[i]-'A'+10;
	}
	For(i,1,((1<<16)-1))
		c[i]=c[i>>1]+(i&1); 
	// pw[i][j] = (i^j);
	For(i,1,16){
		pw[i][0]=1;
		For(j,1,n)pw[i][j]=pw[i][j-1]*i;
	}
	k=read();
	For(i,0,n)For(j,0,k) {
		// 已有j个不同数，还要填i个 
		if(i<k-j)continue;
		Rep(x,k-j,0){
			if((x-(k-j))%2) cnt[i][j]-=C(k-j,x)*pw[x+j][i];
			else cnt[i][j]+=C(k-j,x)*pw[x+j][i];
		}
		cnt[i][j]*=C(16-j,k-j);
	}
	//cout<<cnt[2][0].x<<endl;
	//cnt[1][1]=15;
	modint res=dfs(1,0,1,1);
	cout<<res.x;
	return 0;
}