#include<bits/stdc++.h>
#define ll long long
#define mod 1000000007
#define N 200005
using namespace std;
int read() {
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while('0'<=c&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*f;
}
int n,m,a[N],vst[17],tot;
char s[N];
ll f[N][17];
int main() {
	scanf("%s",s+1);n = strlen(s+1);
	for(int i=1; i<=n; ++i)if(s[i] <= '9')a[i] = s[i]-'0';else a[i] = s[i]-'A'+10;
	m = read();
	for(int i=1; i<=n; ++i) {
		for(int j=1; j<=m; ++j)
			f[i][j] = f[i-1][j]*j+f[i-1][j-1]*(16-j+1);
		if(a[i] >= 1) {
			int sum = 0;
			for(int j=0; j<a[i]; ++j)sum += vst[j];
			f[i][tot] += sum;
			int tmp = a[i]-sum;
			if(i==1)tmp--;
			f[i][tot+1] += max(tmp,0);
		}
		if(i > 1)f[i][1] += 15;
		for(int j=1; j<=m; ++j)f[i][j] %= mod;
		if(!vst[a[i]])vst[a[i]] = 1,tot++;
	}
	cout << (f[n][m]+(tot==m));
}

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

constexpr int Z = 1e9+7;

void add(int cnt[], int &ccnt, int x) {
    cnt[x]++;
    if (cnt[x] == 1) {
        ccnt++;
    }
}

void sub(int cnt[], int &ccnt, int x) {
    cnt[x]--;
    if (cnt[x] == 0) {
        ccnt--;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    string t;
    cin >> t;
    int k;
    cin >> k;

    int n = t.length();
    int a[n];
    for (int i = 0; i < n; i++) {
        a[i] = t[i] <= '9' ? t[i] - '0' : t[i] - 'A' + 10;
    }

    int dp[n][k+1];
    fill(dp[0], dp[n], 0);
    dp[0][0] = 1;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j <= k; j++) {
            dp[i][j] = (1ll * dp[i-1][j] * (k - j) + 1ll * (j == 0 ? 0 : dp[i-1][j-1]) * (16 - k + j)) % Z;
        }
    }

    int ans = 0;
    for (int i = 1; i < n; i++) {
        ans = (0ll + ans + dp[i][k] - dp[i-1][k-1] + Z) % Z;
    }

    int cnt[16];
    fill(cnt, cnt + 16, 0);
    int ccnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = (i == 0 ? 1 : 0); j < a[i]; j++) {
            add(cnt, ccnt, j);
            if (ccnt <= k) {
                (ans += dp[n-1-i][k-ccnt]) %= Z;
            }
            sub(cnt, ccnt, j);
        }
        add(cnt, ccnt, a[i]);
    }

    (ans += (ccnt == k)) %= Z;

    cout << ans << endl;

    return 0;
}
