#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
const int p=1e9+7;
#define rint register int
#define rll register long long
#define ll long long
char s[N];
ll dp[N][20];
int n,k,st[N],a[N];
ll dfs(rint hh,rint re,bool ismx,bool iszero){
	if(re<0||re>hh)return 0;
	if(!hh)return 1;
	if(dp[hh][re]!=-1&&!ismx&&!iszero)return dp[hh][re];
	rll t=0;
	if(!ismx){
		if(!iszero)
			t=dfs(hh-1,re,0,0)*(k-re)+dfs(hh-1,re-1,0,0)*(16-k+re);
		else 
			t=dfs(hh-1,re,0,1)+dfs(hh-1,re-1,0,0)*(15-k+re);
	}else {
		if(iszero)
			t=dfs(hh-1,re,!a[hh],1);
		else {
			if(st[hh+1]&1)t=dfs(hh-1,re,!a[hh],0);
			else t=dfs(hh-1,re-1,!a[hh],0);
		}
		for(rint j=1;j<=a[hh];j++){
			if(st[hh+1]&(1<<j))t+=dfs(hh-1,re,j==a[hh],0);
			else t+=dfs(hh-1,re-1,j==a[hh],0);
		}
	}
	t%=p;
	if(!ismx&&!iszero)dp[hh][re]=t;
	return t;
}
int main(){
	scanf("%s",s+1);
	n=strlen(s+1);
	cin >> k;
	for(rint i=1;i<=n;i++){
		if('0'<=s[i]&&s[i]<='9')a[i]=s[i]-'0';
		else a[i]=s[i]-'A'+10;
		st[i]=st[i-1]|(1<<a[i]);
	}
	reverse(st+1,st+n+1);
	reverse(a+1,a+n+1);
	memset(dp,-1,sizeof(dp));
	printf("%lld\n",dfs(n,k,1,1));
	return 0;
}


#pragma GCC optimize ("O2")
#pragma GCC target ("avx2")
//#include<bits/stdc++.h>
//#include<atcoder/all>
//using namespace atcoder;
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

ll dp[18];
char S[200200];
int suuji(char c) {
	if (c < 'A') return c - '0';
	else return c - ('A' - 10);
}

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


	fread(S, 1, 200200, stdin);
	int K = 0;
	int N = 200200 - 1;
	while (S[N] != ' ') N--;
	int tmp = N + 1;
	while (S[tmp] >= '0') K = K * 10 + S[tmp++] - '0';

	const int mod = 1e9 + 7;
	int k = suuji(S[0]);
	dp[1] = k - 1;
	int kazu = 1 << 15 - k, kazu0 = 1;

	rep1(i, N - 1) {
		for(int j = 16; j >= 1; j--) {
			dp[j] %= mod;
			dp[j + 1] += (16 - j) * dp[j];
			dp[j] = j * dp[j];
		}
		dp[1] += 15;
		int k = suuji(S[i]);
		int k1 = __builtin_popcount(kazu >> 16 - k);
		dp[kazu0] += k1;
		dp[kazu0 + 1] += k - k1;
		kazu0 += !(kazu & 1 << 15 - k);
		kazu |= 1 << 15 - k;
	}

	ll kotae = dp[K];
	if (kazu0 == K) kotae++;
	printf("%lld", kotae % mod);

	Would you please return 0;
}