#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 7;
typedef long long ll;
const ll mod = 1e9 + 7;
string s;
int k, a[N], n;

int work(int x) {
    int ans = 0;
    while (x) {
        if (x & 1) ans++;
        x = x / 2;
    }
    return ans;
}

ll dp[N][20];

ll dfs(int p, int stat, int limit) {
    int cnt = work(stat);
   // cout << p << " " << cnt << " " << stat  << endl;
    if (cnt > k) return 0;
    if (p == n) {
        if (cnt == k) return 1;
        return 0;
    }
    if (!limit && dp[p][cnt] != -1) return dp[p][cnt];
    int maxn = 15;
    if (limit) {
        maxn = a[p];
    }
    ll ans = 0;
    for (int i = 0; i <= maxn; i++) {
        ans += dfs(p + 1, stat | (1 << i), limit && i == maxn);
        ans = ans % mod;
    }
    if (!limit) dp[p][cnt] = ans;
    return ans;

}

void solve() {
    ll ans = 0;
    memset(dp, -1, sizeof(dp));
    for (int i = 0; i < n; i++) {
        int maxn = 15;
        if (i == 0) {
            maxn = a[0];
        }
      //  cout << "Maxn " << maxn << endl;
        for (int j = 1; j <= maxn; j++) {

            ans += dfs(i + 1, (1 << j), i == 0 && j == maxn);
            ans = ans % mod;
        }
    }
    cout << ans << endl;
}

int main() {
    cin >> s >> k;
    n = s.length();
    for (int i = 0; i < s.length(); i++) {
        if (s[i] >= '0' && s[i] <= '9') {
            a[i] = s[i] - '0';
        } else {
            a[i] = s[i] - 'A' + 10;
        }
    }
    solve();
}

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
const int mod=1e9+7;
char s[maxn];int n,vis[300],ans=0,cnt=0;
int dp[maxn][17],f[maxn][17][17];
int mp[300];
void dfs(int pos)
{
	if(pos>n)	return;
	
	for(int i=1;i<=16;i++){
		dp[pos][i]=(dp[pos][i]+1LL*i*dp[pos-1][i]%mod)%mod;
		dp[pos][i]=(dp[pos][i]+1LL*(17-i)*dp[pos-1][i-1]%mod)%mod;
	}
	if(pos!=1){
		dp[pos][1]=(dp[pos][1]+15)%mod;
	}else{
		dp[pos][1]=(dp[pos][1]+(mp[s[pos]]-1))%mod;
	}
	
	if(pos!=1){
		for(int i=0;i<mp[s[pos]];i++){
			if(vis[i]==0)
				dp[pos][cnt+1]=(dp[pos][cnt+1]+1)%mod;
			else
				dp[pos][cnt]=(dp[pos][cnt]+1)%mod;
		}
	}
	
	
	if(vis[mp[s[pos]]]==0)	cnt++,vis[mp[s[pos]]]=1;
	//cout<<pos<<" "<<dp[pos][1]<<endl;
	dfs(pos+1);
}
int main()
{
	for(int i=0;i<10;i++)	mp[i+'0']=i;
	for(int i=0;i<6;i++)	mp[i+'A']=i+10;
	scanf("%s",s+1);n=strlen(s+1);int k;scanf("%d",&k);
	dfs(1);if(cnt==k)	dp[n][k]++;
	cout<<dp[n][k]<<endl;
}