#include<bits/stdc++.h>
#define ll long long
#define mxn 200002
#define mod 1000000007ll
using namespace std;
ll mem[mxn][17][2], n, k;
char str[mxn];
ll dp1(int pos, int rem, bool f)
{
    if(pos==0)return (rem==0);
    ll ret= mem[pos][rem][f];
    if(ret!=-1)return ret;

    ret= 0;
    if(f)
    {
        ret= (k-rem)*dp1(pos-1, rem, f);
        if(rem)ret+= (16-(k-rem))*dp1(pos-1, rem-1, f);
    }
    else ret= 15ll*dp1(pos-1, rem-1, 1);

    return mem[pos][rem][f]= ret%mod;
}
ll dp2(int pos, int rem, bool f, int msk)
{
    if(rem==-1)return 0;
    if(pos==n)return (rem==0);
    ll ret= mem[pos][rem][f];
    if(ret!=-1)return ret;

    ret= 0;
    if(f)
    {
        ret= (k-rem)*dp2(pos+1, rem, f, 0);
        if(rem)ret+= (16-(k-rem))*dp2(pos+1, rem-1, f, 0);
    }
    else
    {
        int let;
        if(str[pos]>='A')let= 10+(str[pos]-'A');
        else let= (str[pos]-'0');

        if(msk&(1<<(let)))ret+= dp2(pos+1, rem, f, msk);
        else ret+= dp2(pos+1, rem-1, f, msk|(1<<(let)));

        for(int i=(pos==0); i<let; i++)
        {
            if(msk&(1<<(i)))ret+= dp2(pos+1, rem, 1, 0);
            else ret+= dp2(pos+1, rem-1, 1, 0);
        }
    }

    return mem[pos][rem][f]= ret%mod;
}
int main()
{
    scanf("%s %lld", str, &k);
    n= strlen(str);

    if(k>n)
    {
        puts("0");
        return 0;
    }

    memset(mem, -1, sizeof mem);

    ll res= 0;
    for(int i=k; i<n; i++)
    res+= dp1(i, k, 0), res%= mod;

    memset(mem, -1, sizeof mem);
    res+= dp2(0, k, 0, 0);
    res%= mod;

    printf("%lld\n", res);

    return 0;
}

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <stack>
#include <vector>
#include <queue>
#include <map>
#define _USE_MATH_DEFINES
#include <math.h>
using namespace std;

#define REP(i,n) for(int i = 0; i < (int)n; i++)

#define V vector<int>
#define P pair<int,int>
#define INF 1000000007
#define MOD	1000000007
typedef long long LL;

string N;
int K;
LL dp[200010][20];

int char_int(char c) {
	int res = 0;
	if ('0' <= c && c <= '9') {
		res = c - '0';
	}
	else {
		res = c - 'A' + 10;
	}
	return res;
}


void cal() {
	int kcnt = 0;
	bool used[16];
	REP(i, 16)	used[i] = false;
	REP(i, N.size()) {
		int c = char_int(N[i]);
		if (i == 0) {
			dp[i][1] = c - 1;
			used[c] = true;
			kcnt++;
			continue;
		}
		for (int j = 1; j <= K; j++) {
			dp[i][j] += dp[i - 1][j] * j;
			dp[i][j] += dp[i - 1][j - 1] * (16 - (j - 1));
			dp[i][j] %= MOD;
		}
		dp[i][1] += 15;

		for (int k = 0; k < c; k++) {
			if (used[k])	dp[i][kcnt]++;
			else dp[i][kcnt + 1]++;
		}
		if (!used[c]) {
			used[c] = true;
			kcnt++;
		}
	}
	dp[N.size()-1][kcnt]++;
}

int main() {
	cin >> N >> K;
	cal();
	cout << dp[N.size() - 1][K] % MOD << endl;
}