#include<bits/stdc++.h>
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)? EOF:*p1++)
using namespace std;
typedef long long ll;
const int N=2e5+5,mod=1e9+7;
int n,k;
ll f[N][2][2][17];
bool vs[N][2][2][17];
int cnt[N],bk[N][17];
char s[N];
int gt(char x)
{
	if(x<='9') return x-'0';
	return x-'A'+10;
}
ll dfs(int st,int f1,int f2,int nm)
{
	if(st>n) return f2&&(nm==k);
	if(vs[st][f1][f2][nm]) return f[st][f1][f2][nm];
	vs[st][f1][f2][nm]=1;
	ll &lp=f[st][f1][f2][nm],i,j;
	if(f1)
	{
		lp=(lp+dfs(st+1,1,1,cnt[st]))%mod;
		for(i=0,j=gt(s[st]);i<j;i++)
			lp=(lp+dfs(st+1,0,f2|!!i,nm+(!bk[st-1][i])))%mod;
		return lp;
	}
	if(!f2) return lp=(15*dfs(st+1,0,1,1)+dfs(st+1,0,0,0))%mod;
	return lp=((16-nm)*dfs(st+1,0,1,nm+1)+nm*dfs(st+1,0,1,nm))%mod;
}
int main()
{
	int i,j;
	scanf("%s%d",s+1,&k),n=strlen(s+1);
	for(i=1;i<=n;i++)
		cnt[i]=cnt[i-1]+(!bk[i-1][gt(s[i])]),memcpy(bk[i],bk[i-1],sizeof(bk[i])),bk[i][gt(s[i])]=1;
	cout<<dfs(1,1,0,0);
	return 0;
}
#include <iostream>

using namespace std;
using ll = long long;

const int kMod = 1e9 + 7;
const int kMaxN = 2e5 + 1;

string s;
int a[kMaxN];
ll c[20][20], dp[kMaxN][20];
ll ans, k, n, fl, b[20];

ll ksm(ll a, ll b) {
  ll x = 1;
  for (; b; b /= 2, a = a * a % kMod) {
    if (b % 2 == 1) {
      x = x * a % kMod;
    }
  }
  return x;
}

int q() {
  int cnt = 0, i;
  for (i = 0; i <= 15; i++) {
    cnt += (b[i] > 0);
  }
  return cnt;
}
int main() {
  int i, t1, j, l;
  cin >> s;
  n = s.size();
  for (i = 0; i < n; i++) {
    if (s[i] >= 'A') {
      a[i + 1] = s[i] - 'A' + 10;
    } else {
      a[i + 1] = s[i] - '0';
    }
  }
  cin >> k;
  dp[1][1] = a[1] - 1;
  for (i = 1; i < n; i++) {
    dp[i + 1][1] = 15, b[a[i]]++;
    for (j = 1; j <= k; j++) {
      dp[i + 1][j] = (dp[i + 1][j] + dp[i][j] * j) % kMod;
      dp[i + 1][j + 1] = (dp[i + 1][j + 1] + dp[i][j] * (16 - j)) % kMod;
    }
    t1 = q();
    for (j = 0; j < a[i + 1]; j++) {
      if (b[j] == 0) {
        dp[i + 1][t1 + 1]++;
      } else {
        dp[i + 1][t1]++;
      }
    }
  }
  b[a[n]]++, dp[n][q()]++;
  cout << dp[n][k] % kMod;
  return 0;
}