#include<bits/stdc++.h>
#define ll long long 
using namespace std;

const int N = 200010, mod = 1e9 + 7;

ll dp[N][20], k, num[N];
char s[N];

ll dfs(int pos, bool limit, bool lead, int cnt, ll state){
	if(!pos)	return cnt == k;
	if(cnt > k)	return 0;
	if(!limit && !lead && ~dp[pos][cnt])	return dp[pos][cnt];
	ll ans = 0;
	int up = limit ? num[pos] : 15;
	for(int i = 0; i <= up; ++ i){
		if(lead && !i)	ans = (ans + dfs(pos - 1, limit && i == up, true, 0, 0)) % mod;
		else{
			if((state >> i) & 1)	ans = (ans + dfs(pos - 1, limit && i == up, false, cnt, state)) % mod;
			else	ans = (ans + dfs(pos - 1, limit && i == up, false, cnt + 1, state | (1 << i))) % mod;
		}
	}
	if(!limit && !lead)	dp[pos][cnt] = ans;
	return ans;
}

ll solve(){
	int len = strlen(s + 1);
	for(int i = 1, j = len; i < j; ++ i, -- j)	swap(s[i], s[j]);
	for(int i = 1; i <= len; ++ i){
		if(s[i] >= '0' && s[i] <= '9')	num[i] = s[i] - '0';
		else	num[i] = s[i] - 'A' + 10;
	}
	return dfs(len, true, true, 0, 0);
} 

int main(){
	scanf("%s", s + 1);
	cin >> k;
	memset(dp, -1, sizeof dp);
	cout << solve();
	return 0;
}
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

#define rep(i,n) for (long long i = 0; i < (n); ++i)
#define INF LONG_MAX/3
#define DIV 1000000007
//#define DIV 998244353

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

long long kaidan[10000000];

void kaical(long long n){
	kaidan[0] = 1;
	for(long long i = 1; i < n; i++){
		kaidan[i] = kaidan[i-1] * i;
		kaidan[i] %= DIV;
	}
}

long long modpow(long long ori, long long po){
	long long res = 1;
	while(po > 0){
		if(po&1){
			res *= ori;
			res %= DIV;
		}
		ori *= ori;
		ori %= DIV;
		po >>= 1;
	}
	return res;
}

//nCk
long long combination(long long n, long long k){
	if(n == 0 && k == 0)return 1;
	if(n < k || n < 0)return 0;
	long long n_kai = kaidan[n];
	long long k_kai = kaidan[k];
	long long nmk_kai = kaidan[n-k];

	long long ans = n_kai * modpow(k_kai, DIV - 2);
	ans %= DIV;
	ans *= modpow(nmk_kai, DIV-2);
	ans %= DIV;
	return ans;
}

ll tonum(char ch) {
	if(ch >= '0' && ch <= '9') return ch - '0';
	return ch - 'A' + 10;
}

string S;
ll K;

//すでに使った、これからつかう、残り長さ
ll cal(ll idx, ll num) {
	ll used = num;
	ll willuse = K - used;
	ll leng = S.size() - idx;

	//if(willuse == 0) return 1;
	if(used > K) return 0;
	if(willuse < 0) return 0;
	if(willuse > leng) return 0;

	ll ret = 0;
	rep(unused, willuse + 1) {
		if(unused%2 == 0) {
			ret += modpow(K - unused, leng) * combination(willuse, unused);
			ret %= DIV;
			ret += DIV;
			ret %= DIV;
		} else {
			ret -= modpow(K - unused, leng) * combination(willuse, unused);
			ret %= DIV;
			ret += DIV;
			ret %= DIV;
		}
	}

	//will useの選び方
	ret *= combination(16 - used, willuse);
	ret %= DIV;
	ret += DIV;
	ret %= DIV;

	//cout << "ret " << ret << endl;
	return ret;
}

ll memo[200005][20];

ll cal2(ll idx, ll num) {
	if(memo[idx][num] >= 0) return memo[idx][num];

	if(idx == S.size()) {
		if(num == K) return 1;
		return 0;
	}


	ll newnum = 16 - num;
	ll ret = 0;
	//同じのとる
	ret += num * cal2(idx+1, num);
	ret %= DIV;

	//新しいのとる
	if(newnum > 0) {
		ret += newnum * cal2(idx+1, num + 1);
		ret %= DIV;
	}
	memo[idx][num] = ret;
	return ret;
}

int main(){
	cin >> S >> K;

	kaical(20);
	rep(i,200005) rep(j, 20) memo[i][j] = -1;

	ll ans = 0;
	set<ll> used;
	rep(i, S.size()) {
		ll num = tonum(S[i]);

		//ここまでゼロでここから始まる
		if(i != 0) {
			ans += 15 * cal(i + 1, 1);
			ans %= DIV;
		}

		//ここで下回る
		rep(use, num) {
			//0から始めるのはなし
			if(use == 0 && i == 0) continue;
			if(used.count(use)) {
				ans += cal(i+1, used.size());
			} else {
				ans += cal(i+1, used.size()+1);
			}
			ans %= DIV;
			//cout << "curans = " << ans << endl;
		}
		//cout << endl;

		//ギリギリをいく
		used.insert(tonum(S[i]));
		//if(used.size() > K) {
		//	break;
		//}
	}

	if(used.size() == K) {
		ans++;
	}
	ans %= DIV;
	ans += DIV;
	ans %= DIV;

	cout << ans << endl;
}
