#include<bits/stdc++.h>

using namespace std;
#define ll long long
#define ull unsigned long long
#define i128 __int128
#define mp make_pair
#define mt make_tuple
#define tp(pos, name) get<pos>(name)
#define ld long double
#define VNAME(name) (#name)
typedef pair<int, int> pii;
typedef priority_queue<int, vector<int>, greater<int> > small_heap;
typedef priority_queue<int> big_heap;
typedef tuple<int, int, int> mkgroups;

void debug_out() { cout << '\n'; }

template<typename T, typename... R>
void debug_out(const T &f, const R &... r) {
    cout << f << " ";
    debug_out(r...);
}

template<typename A, typename B>
ostream &operator<<(ostream &out, const pair<A, B> &a) {
    out << "(" << a.first << "," << a.second << ")";
    return out;
}

template<typename Tuple, size_t N>
struct tuple_print {
    static void print(const Tuple &t, std::ostream &os) {
        tuple_print<Tuple, N - 1>::print(t, os);
        os << ", " << std::get<N - 1>(t);
    }
};

template<typename Tuple>
struct tuple_print<Tuple, 1> {
    static void print(const Tuple &t, std::ostream &os) { os << "(" << std::get<0>(t); }
};

template<typename... Args>
ostream &operator<<(ostream &os, const tuple<Args...> &t) {
    tuple_print<decltype(t), sizeof...(Args)>::print(t, os);
    return os << ")";
}

template<typename T>
ostream &operator<<(ostream &out, const vector<T> &a) {
    out << "[";
    bool first = true;
    for (auto &v : a) {
        out << (first ? "" : ", ");
        out << v;
        first = 0;
    }
    out << "]";
    return out;
}

template<typename T, class Cmp>
ostream &operator<<(ostream &out, const set<T, Cmp> &a) {
    out << "{";
    bool first = true;
    for (auto &v : a) {
        out << (first ? "" : ", ");
        out << v;
        first = 0;
    }
    out << "}";
    return out;
}

template<typename U, typename T, class Cmp>
ostream &operator<<(ostream &out, const map<U, T, Cmp> &a) {
    out << "{";
    bool first = true;
    for (auto &p : a) {
        out << (first ? "" : ", ");
        out << p.first << ":" << p.second;
        first = 0;
    }
    out << "}";
    return out;
}

template<typename Arg1>
void __f(const char *name, Arg1 &&arg1) { cerr << name << ": " << arg1 << endl; }

template<typename Arg1, typename... Args>
void __f(const char *names, Arg1 &&arg1, Args &&... args) {
    const char *comma = strchr(names + 1, ',');
    cerr.write(names, comma - names) << ": " << arg1 << " |";
    __f(comma + 1, args...);
}

const ll mod = 1e9 + 7;
const int N = 1e6 + 100;
int T;
string str;
int n;

int main() {
    ios::sync_with_stdio(false);
    cin >> str >> n;
    vector<int> v;
    for (auto x:str) {
        if (isdigit(x))v.push_back(x - '0');
        else v.push_back(x - 'A' + 10);
    }
    vector<vector<ll>> f(str.size() + 1, vector<ll>(18, 0));
    int state = 0;
    for (int i = 0; i < str.size(); i++) {
        for (int j = 1; j <= 16; j++) {
            f[i + 1][j] = (f[i + 1][j] + f[i][j] * 1ll * j) % mod;
            f[i + 1][j + 1] = (f[i + 1][j + 1] + f[i][j] * 1ll * (16 - j)) % mod;
        }
        f[i + 1][1] = (f[i + 1][1] + f[i][0] * 15ll) % mod;
        f[i + 1][0] = (f[i + 1][0] + f[i][0]) % mod;
        for (int j = 0; j < v[i]; j++) {
            int cut = state;
            if (i || j)cut |= (1 << j);
            f[i + 1][__builtin_popcount(cut)] += 1;
        }
        state |= (1 << v[i]);
    }
    cout << f[str.size()][n] + (__builtin_popcount(state) == n);
    return 0;
}
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
 
using namespace std;
 
const int maxn = 2e5 + 50, INF = 0x3f3f3f3f, mod = 1e9 + 7;
 
inline int read () {
	register int x = 0, w = 1;
	register char ch = getchar ();
	for (; ch < '0' || ch > '9'; ch = getchar ()) if (ch == '-') w = -1;
	for (; ch >= '0' && ch <= '9'; ch = getchar ()) x = x * 10 + ch - '0';
	return x * w;
}
 
int n, k, ans, a[maxn], s[maxn], f[maxn][17];
char str[maxn];
 
inline int addmod (register int a, register int b) { 
	return a += b, a >= mod ? a - mod : a;
}
 
inline int DFS (register int now, register int cnt, register bool flag0, register bool flag1, register int ans = 0) {
	if (cnt < 0 || cnt > n - now + 1) return 0;
	if (now == n + 1) return 1;
	if (! flag0 && ! flag1 && f[now][cnt] != -1) return f[now][cnt];
	if (flag1) {
		for (register int i = 0; i <= a[now]; i ++) {
			if (s[now - 1] & 1 << i) ans = addmod (ans, DFS (now + 1, cnt, 0, i == a[now]));
			else ans = addmod (ans, DFS (now + 1, cnt - 1, 0, i == a[now]));
		}
	} else if (flag0) ans = addmod (ans, addmod (DFS (now + 1, cnt, 1, 0), 1ll * DFS (now + 1, cnt - 1, 0, 0) * (15 - k + cnt) % mod));
	else ans = addmod (ans, addmod (1ll * DFS (now + 1, cnt, 0, 0) * (k - cnt) % mod, 1ll * DFS (now + 1, cnt - 1, 0, 0) * (16 - k + cnt) % mod));
	if (! flag0 && ! flag1) return f[now][cnt] = ans;
	else return ans;
}
 
int main () {
	scanf ("%s", str + 1), n = strlen (str + 1), k = read(), memset (f, -1, sizeof f);
	for (register int i = 1; i <= n; i ++) {
		if (str[i] >= '0' && str[i] <= '9') a[i] = str[i] - '0';
		else a[i] = str[i] - 'A' + 10;
		s[i] = s[i - 1] | 1 << a[i];
	}
	for (register int i = 0; i <= a[1]; i ++) {
		if (i == 0) ans = addmod (ans, DFS (2, k, 1, 0));
		else if (i == a[1]) ans = addmod (ans, DFS (2, k - 1, 0, 1));
		else ans = addmod (ans, DFS (2, k - 1, 0, 0));
	}
	return printf ("%d\n", ans), 0;
}