#include<bits/stdc++.h>
#define mz 1000000007
using namespace std;

int len;
long long dp[200005][20][20];
char s[200006];
long long ans=0;
bool life[20];

void go(int l,bool f,int k,int now)
{
	int ff;
	if(now>k)
		return ;
	if(f==1)
		ff=s[len-l];
	else
		ff=15;
	if(l==1)
	{
		int tt=0;
		if(k==now)
		{
			for(int i=0;i<=ff;i++)
				if(life[i])
					tt++;
		}
		else if(now==k-1)
		{
			for(int i=(now==0);i<=ff;i++)
				if(!life[i])
					tt++;
		}
		ans=(ans+tt)%mz;
		return ;
	}
	if(f==1)
	{
		for(int i=0;i<ff;i++)
		{
			if(life[i] || (i==0 && now==0))
				go(l-1,0,k,now);
			else
			{
				life[i]=1;
				go(l-1,0,k,now+1);
				life[i]=0;
			}
		}
		if(life[ff]==0)
			now++;
		life[ff]=1;
		go(l-1,1,k,now);
	}
	else
	{
		if(now==0)
		{
			go(l-1,0,k,0);
			ans=(ans+15*dp[l-1][k][1])%mz;
		}
		else
		{
			ans=(ans+dp[l][k][now])%mz;
		}
	}
}

int main()
{
	for(int i=1;i<=16;i++)
		dp[0][i][i]=1;
	for(int i=1;i<=200001;i++)
		for(int j=1;j<=16;j++)
			for(int k=1;k<=j;k++)
				dp[i][j][k]=(dp[i-1][j][k]*j+dp[i-1][j-1][k]*(17-j))%mz;
	scanf("%s",s);
	int k;
	scanf("%d",&k);
	len=strlen(s);
	for(int i=0;i<len;i++)
	{
		if(s[i]<='9' && s[i]>='0')
			s[i]-='0';
		else
			s[i]-='A'-10;
	}
	go(len,1,k,0);
	printf("%lld\n",ans);
	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;

	rep1(i, N - 1) {
		if (!(i & 7)) for (int j = 2; j <= 16; j++) dp[j] %= mod;
		for (int j = 16; j >= 1; j--) {
			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);
		int kazu0 = __builtin_popcount(kazu);
		dp[kazu0] += k1;
		dp[kazu0 + 1] += k - k1;
		kazu |= 1 << 15 - k;
	}

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

	Would you please return 0;
}