#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define rep(i,a,b) for (int i=(a); i<=(b); i++)
#define drep(i,a,b) for (int i=(b); i>=(a); i--)
#define erep(e,u) for (int e=Head[u]; e; e=Next[e])
#define arep(i,A) for (auto i : A)
#define push_back pb
#define print(x,c) printf ("%d%c", x, c);
typedef long long ll;
typedef pair <int, int> pii;
const int N = 2e5 + 5;
int K, n, F[233], cnt[N], dp[N][17], ans; char s[N]; bitset <16> f[N];
inline int PLUS(int x, int y) {
	x += y;
	return x >= MOD ? x - MOD : x;
}
inline void readseq(int n, int *a) {
	rep (i, 1, n)
		scanf ("%d", a + i);
}
int main() {
	for (int i=0; i<=9; i++)
		F['0'+i] = i;
	for (int i='A'; i<='F'; i++)
		F[i] = i - 'A' + 10;
	scanf ("%s%d", s+1, &K), n = strlen(s + 1);
	for (int i=1; i<=n; i++)
		f[i] = f[i-1], f[i][F[s[i]]] = 1, cnt[i] = f[i]. count();
	for (int i=1; i<=n; i++) {
		for (int j=1; j<=16; j++)
			dp[i][j] = (1ll * dp[i-1][j-1] * (16 - j + 1) + 1ll * dp[i-1][j] * j) % MOD;
		for (int j=i==1?1:0; j<F[s[i]]; j++)
			dp[i][cnt[i-1]+1-(bool)f[i-1][j]] = PLUS(dp[i][cnt[i-1]+1-(bool)f[i-1][j]], 1);
		if (i > 1)
			dp[i][1] = PLUS(dp[i][1], 15);
	} ans = PLUS(dp[n][K], (cnt[n] == K));
	return cout << ans << endl, 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;
}
