#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

char S[200200]; int K, bc[1 << 16], tr[200200], dig[200200];

const long long mod = 1000000007;
long long prv[17][17], nxt[17][17];

int main()
{
	scanf ("%s %d", S, &K);
	int l = 0;
	while (S[l]) l++;

	for (int i = 0; i < l; i++){
		if ('0' <= S[i] && S[i] <= '9') tr[i] = S[i] - '0';
		else tr[i] = S[i] - 'A' + 10;
		dig[i + 1] = dig[i] | (1 << tr[i]);
	}
	for (int i = 1; i < (1 << 16); i++) bc[i] = bc[i - (i & (-i))] + 1;
	for (int i = 0; i <= 16; i++) prv[i][i] = 1;

	long long ans = (bc[dig[l]] == K);
	for (int i = l - 1; i >= 0; i--){
		if (i) ans = (ans + prv[1][K] * 15) % mod;
		for (int s = 0; s < tr[i]; s++){
			if (s == 0 && i == 0) continue;
			int b = bc[dig[i] | (1 << s)];
			ans = (ans + prv[b][K]) % mod;
		}
		memset(nxt, 0, sizeof(nxt));
		for (int j = 0; j <= 16; j++){
			for (int k = j; k <= 16; k++){
				nxt[j][k] = (nxt[j][k] + prv[j][k] * k) % mod;
				if (k < 16) nxt[j][k + 1] = (nxt[j][k + 1] + prv[j][k] * (16 - k)) % mod;
			}
		}
		memcpy(prv, nxt, sizeof(nxt));
	}

	printf ("%lld\n", ans);
	return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int N=5005,mod=998244353;
int n,m,ans,v[N][N];
int qp(int a,int b)
{
	if(v[a][b]!=-1)
		return v[a][b];
	int ma=a,mb=b;
	int ans=1;while(b){if(b&1)ans=1ll*ans*a%mod;a=1ll*a*a%mod;b>>=1;}
	v[ma][mb]=ans;
	return ans;
}
int main()
{
	memset(v,-1,sizeof(v));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		ans=(ans+1ll*qp(m-1,i-1)*qp(m,n-i))%mod;
	ans=1ll*ans*m%mod;
	for(int i=0;i<=n-2;i++)
	{
		int t=n-1-i;
		for(int j=1;j<=m;j++)
			ans=(ans+1ll*t*(qp(m-1,i)+mod-qp(j-1,i))%mod*qp(m,n-2-i))%mod;
	}
	printf("%d\n",ans);
	return 0;
}
