#include<bits/stdc++.h>
const int N=200010,mod=1e9+7;
char s[N];
int c[N],fac[N],f[17][N],n,KK,a[17],cnt,g[N][17],C[17][17];
int qp(int x,int y)
{
	int ans=1;
	for(;y;y >>=1,x=1ll*x*x%mod)
		if(y&1)ans=1ll*ans*x%mod;
	return ans;
}
void ins(int x)
{
	if(!a[x]++)cnt++;
}
void eras(int x)
{
	if(!--a[x])
		cnt--;
}	
int main()
{
	scanf("%s",s+1),n=strlen(s+1);
	scanf("%d",&KK);
	for(int i=0;i<=16;i++)
		C[i][0]=C[i][i]=1;
	for(int i=1;i<=16;i++)
		for(int j=1;j<i;j++)
			C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
	for(int i=fac[0]=1;i<=16;i++)
		fac[i]=1ll*fac[i-1]*i%mod;
	g[0][0]=1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=i&&j<=16;j++)
			g[i][j]=(1ll*j*g[i-1][j]+g[i-1][j-1])%mod;
	
	f[KK][n+1]=1;
	for(int j=0;j<=KK;j++)
		for(int i=n;i;i--)
			for(int k=0;k<=j;k++)
				f[j][i]=(f[j][i]+1ll*C[16-j][KK-j]*C[j][k]%mod*g[n-i+1][KK-j+k]%mod*fac[KK-j+k])%mod;
	for(int i=1;i<=n;i++)
		c[i]=(isdigit(s[i])?s[i]-'0':s[i]-'A'+10);
	int ans=0;
	for(int i=1;i<=n;ins(c[i++]))
		for(int j=i==1;j<=c[i]-(i!=n);j++)
			ins(j),ans=(ans+f[cnt][i+1])%mod,eras(j);
	for(int i=2;i<=n;i++)ans=(ans+1ll*f[1][i+1]*15)%mod;
	printf("%d\n",ans);
	return 0;
}
#include <bits/stdc++.h>
#define DEBUG if(0)
typedef long long ll;
using namespace std;

const int maxSz = 2e5, maxCnt = 16;
const ll mod = 1e9 + 7;
ll dp[maxSz][maxCnt + 1][2][2];

char s[maxSz + 1];
int a[maxSz];
int sz, k;

ll solve(int mask, int pos, bool lmt, bool started) {
    int cnt = __builtin_popcount(mask);
    if (cnt > k) return 0;
    if (pos == sz) return cnt == k && started;

    ll &ans = dp[pos][cnt][lmt][started];
    if (ans != -1) return ans;

    ans = 0;
    int llmt = (lmt ? a[pos] : 15);
    for (int i = 0; i <= llmt; i++)
        ans = (ans + solve((!i && !started) ? mask : mask | (1 << i), pos + 1, lmt & (i == llmt), started | (i > 0))) % mod;
    return ans;
}

int main() {
    cin >> s >> k;
    sz = strlen(s);
    for (int i = 0; i < sz; i++) {
        a[i] = s[i] - (isdigit(s[i]) ? '0' : 'A' - 10);
    }

    DEBUG
    {
        printf("%s\n", s);
        for (int i = 0; i < sz; i++)
        printf("%d ", a[i]);
        printf("\n");
    }
    memset(dp, -1, sizeof(dp));
    cout << solve(0, 0, 1, 0) << endl;

  return 0;
}
