#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
const int mod=1e9+7;
int n,m;
int C[17][17];
char s[N];
int a[N];
int w[200];
inline int po(int x,int k){
	int ret=1;
	while(k){
		if(k&1) ret=1ll*ret*x%mod;
		x=1ll*x*x%mod;
		k>>=1;
	}
	return ret;
}
inline int calc(int f,int c){
	if(c<m-f) return 0;
	int ret=0;
	for(int i=m;i>=f;i--){
		if(m-i&1) ret=(ret-1ll*C[m-f][i-f]*po(i,c)%mod+mod)%mod;
		else ret=(ret+1ll*C[m-f][i-f]*po(i,c))%mod;
	}
	return ret;
}
int cnt[17],tot;
int main(){
	int i,j;
	for(i='0';i<='9';i++) w[i]=i-'0';
	for(i='A';i<='F';i++) w[i]=i-'A'+10;
	for(i=0;i<17;i++){
		for(j=0;j<17;j++){
			if(j==0||j==i) C[i][j]=1;
			else C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
		}
	}
	cin>>(s+1);n=strlen(s+1);
	for(i=1;i<=n;i++) a[i]=w[s[i]];
	cin>>m;
	int ans=0;
	for(i=2;i<=n;i++){
		ans=(ans+1ll*C[15][m]*calc(0,n-i+1))%mod;
		ans=(ans+1ll*C[15][m-1]*(m-1)%mod*calc(1,n-i))%mod;
	}
	ans=(ans+1ll*C[15][m-1]*(a[1]-1)%mod*calc(1,n-1))%mod;
	for(i=1;i<n;i++){
		cnt[a[i]]++;if(cnt[a[i]]==1) tot++;
		if(tot>m) break;
		if(a[i+1]==0) continue;
		int s1=0,s2=0;
		for(j=0;j<a[i+1];j++)
			if(cnt[j]) s1++;
		s2=tot-s1;
		int t1=a[i+1]-s1,t2=16-a[i+1]-s2;
		for(j=0;j<=t1&&j<=m-tot;j++)
			ans=(ans+1ll*C[t1][j]*C[t2][m-tot-j]%mod*(1ll*s1*calc(tot,n-i-1)+1ll*j*calc(tot+1,n-i-1)))%mod;
	}
	cnt[a[n]]++;if(cnt[a[n]]==1) tot++;
	if(tot==m) ans=(ans+1)%mod;
	cout<<ans;
	return 0;
}

#include <iostream>
#include <iomanip>
#include <fstream>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <algorithm>
#include <numeric>
#include <utility>
#include <random>
#include <chrono>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>

using namespace std;

using LL = long long;
using ULL = unsigned long long;
using PII = pair<int, int>;
using PIL = pair<int, LL>;
using PLL = pair<LL, LL>;
const int mod = 1e9 + 7;
// const int mod = 998244353;

inline void quickread() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

string s;
int add[200010], keep[200010], has[200010];
int f[200010][2][17];
int k;

inline int tonum(char c) {
    return (c <= '9' ? c - '0' : c - 'A' + 10);
}

inline int dfs(int pos, bool bound, int diff) {
    if (pos == s.size()) {
        return diff == k;
    }
    if (diff > k) {
        return 0;
    }

    if (f[pos][bound][diff] != -1) {
        return f[pos][bound][diff];
    }
    f[pos][bound][diff] = 0;
    
    if (!diff) {
        f[pos][bound][diff] = dfs(pos + 1, false, 0);
    }
    if (bound) {
        f[pos][bound][diff] += dfs(pos + 1, true, has[pos]);
        f[pos][bound][diff] %= mod;
        f[pos][bound][diff] += (LL)(diff ? add[pos] : add[pos] - 1) * dfs(pos + 1, false, diff + 1) % mod;
        f[pos][bound][diff] %= mod;
        f[pos][bound][diff] += (LL)keep[pos] * dfs(pos + 1, false, diff) % mod;
        f[pos][bound][diff] %= mod;
    }
    else {
        f[pos][bound][diff] += (LL)((diff ? 16 : 15) - diff) * dfs(pos + 1, false, diff + 1) % mod;
        f[pos][bound][diff] %= mod;
        f[pos][bound][diff] += (LL)diff * dfs(pos + 1, false, diff) % mod;
        f[pos][bound][diff] %= mod;
    }

    return f[pos][bound][diff];
}

inline void work() {
    cin >> s >> k;
    unordered_set<int> o; 
    for (int i = 0; i < s.size(); ++i) {
        int jm = tonum(s[i]);
        for (int j = 0; j < jm; ++j) {
            if (!o.count(j)) {
                ++add[i];
            }
            else {
                ++keep[i];
            }
        }
        o.insert(jm);
        has[i] = o.size();
    }

    memset(f, -1, sizeof(f));
    int ans = dfs(0, 1, 0);
    cout << ans << "\n";
}

int main() {
    // freopen("input.txt", "r", stdin);
    quickread();
    work();
    return 0;
}