#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
string to_string(string s) { return '"' + s + '"'; }
string to_string(const char* s) { return to_string(string(s)); }
string to_string(bool b) { return to_string(int(b)); }
string to_string(vector<bool>::reference b) { return to_string(int(b)); }
string to_string(char b) { return "'" + string(1, b) + "'"; }
template <typename A, typename B>
string to_string(pair<A, B> p) { return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; }
template <typename A>
string to_string(A v) {
	string res = "{";
	for (const auto& x : v) res += (res == "{" ? "" : ", ") + to_string(x);
	return res + "}";
}
void debug() { cerr << endl; }
template <typename Head, typename... Tail>
void debug(Head H, Tail... T) {
	cerr << " " << to_string(H);
	debug(T...);
}
#define db(...) cerr << "[" << #__VA_ARGS__ << "]:", debug(__VA_ARGS__)
#else
#define db(...) 42
#endif
typedef long long ll;
typedef long double ld;
const int MOD = 1000000007;
struct Mint {
	int val;
	Mint() { val = 0; }
	Mint(ll x) {
		val = (-MOD <= x && x < MOD) ? x : x % MOD;
		if (val < 0) val += MOD;
	}
	template <typename U>
	explicit operator U() const { return (U)val; }
	friend bool operator==(const Mint& a, const Mint& b) { return a.val == b.val; }
	friend bool operator!=(const Mint& a, const Mint& b) { return !(a == b); }
	friend bool operator<(const Mint& a, const Mint& b) { return a.val < b.val; }
	Mint& operator+=(const Mint& m) { if ((val += m.val) >= MOD) val -= MOD; return *this; }
	Mint& operator-=(const Mint& m) { if ((val -= m.val) < 0) val += MOD; return *this; }
	Mint& operator*=(const Mint& m) { val = (ll)val * m.val % MOD; return *this; }
	friend Mint modex(Mint a, ll p) {
		assert(p >= 0);
		Mint ans = 1;
		for (; p; p >>= 1, a *= a) if (p & 1) ans *= a;
		return ans;
	}
	Mint& operator/=(const Mint& m) { return *this *= modex(m, MOD - 2); }
	Mint& operator++() { return *this += 1; }
	Mint& operator--() { return *this -= 1; }
	Mint operator++(int) { Mint result(*this); *this += 1; return result; }
	Mint operator--(int) { Mint result(*this); *this -= 1; return result; }
	Mint operator-() const { return Mint(-val); }
	friend Mint operator+(Mint a, const Mint& b) { return a += b; }
	friend Mint operator-(Mint a, const Mint& b) { return a -= b; }
	friend Mint operator*(Mint a, const Mint& b) { return a *= b; }
	friend Mint operator/(Mint a, const Mint& b) { return a /= b; }
	friend ostream& operator<<(ostream& os, const Mint& x) { return os << x.val; }
	friend string to_string(const Mint& b) { return to_string(b.val); }
};
vector<Mint> fac(1, 1), invfac(1, 1);
Mint binom(int n, int k) {
	if (k < 0 || k > n) return 0;
	while (fac.size() <= n) {
		fac.push_back(fac.back() * fac.size());
		invfac.push_back(1 / fac.back());
	}
	return fac[n] * invfac[k] * invfac[n - k];
}
char n[200005];
int main() {
	binom(16, 0);
	int k;
	scanf("%s%d", n, &k);
	// [alr][...l ?...], want exactly k distinct.
	// each non-alr has to appear at least once.
	auto calc = [&](int l, int alr) -> Mint {
		if (alr > k) return 0;
		Mint ret = 0;
		for (int i = 0; i <= k - alr; ++i) {
			Mint v = modex(Mint(k - i), l) * binom(k - alr, i);
			if (i & 1) ret -= v;
			else ret += v;
		}
		return ret;
	};
	int m = strlen(n);
	vector<bool> has(16);
	int dis = 0;
	Mint ans = 0;
	for (int i = 1; i < m; ++i) {
		ans += calc(i, 0) * binom(16, k);
		ans -= calc(i - 1, 1) * binom(15, k - 1);
	}
	for (int i = 0; i < m; ++i) {
		int val = n[i] >= '0' && n[i] <= '9' ? n[i] - '0' : n[i] - 'A' + 10;
		for (int j = (i == 0 ? 1 : 0); j < val; ++j) {
			int ndis = dis;
			if (!has[j]) ndis++;
			ans += calc(m - i - 1, ndis) * binom(16 - ndis, k - ndis);
		}
		if (!has[val]) {
			dis++;
			has[val] = true;
		}
	}
	if (dis == k) ans++;
	printf("%d\n", ans.val);
}

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;
typedef long long LL;
string s;
LL dp[N][20], v[N];
LL const mod = 1e9 + 7;
int k;
int main() {
    cin >> s >> k;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] >= '0' && s[i] <= '9')
            v[i] = s[i] - '0';
        else
            v[i] = 10+s[i] - 'A';
    }
    LL state = 0;
    for (LL i = 0; i < s.size(); i++) {
        for (LL j = 1; j <= 16; ++j) {
            dp[i + 1][j] = (dp[i + 1][j] + (LL)dp[i][j] * j % mod) % mod;
            dp[i + 1][j + 1] =
                (dp[i + 1][j + 1] + (LL)dp[i][j] * (16 - j) % mod) % mod;
        }
        dp[i + 1][1] = (dp[i + 1][1] + (LL)dp[i][0] * 15 % mod) % mod;
        dp[i + 1][0] = (dp[i + 1][0] + dp[i][0]) % mod;
        for (LL j = 0; j < v[i]; ++j) {
            LL nstate = state;
            if (i || j) nstate |= (1 << j);
            dp[i + 1][__builtin_popcount(nstate)] += 1;
        }
        state |= (1 << v[i]);
    }
    cout << dp[s.size()][k] + (__builtin_popcount(state) == k) << endl;
    return 0;
}