#include <algorithm>
#include <iostream>

using namespace std;

const int kMaxN = 2e5 + 1;
const int kM = 1e9 + 7;
const int kA = 16;

string s;
long long f[kMaxN][kA + 1], g[kMaxN][kA + 1];
int k, n, t, ans, c[kA];

void C1() {
  f[1][1] = kA - 1;
  for (int i = 1; i < n; i++) {
    for (int j = 1; j <= k; j++) {
      f[i][j] = (f[i][j] + f[i - 1][j] * j + f[i - 1][j - 1] * (17 - j)) % kM;
    }
    ans = (ans + f[i][k]) % kM;
  }
}

void C2() {
  g[1][1] = -1;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= k; j++) {
      g[i][j] = (g[i][j] + g[i - 1][j] * j + g[i - 1][j - 1] * (17 - j)) % kM;
    }
    for (int j = 0; j < s[i - 1]; j++) {
      t += !c[j]++;
      g[i][t] = (g[i][t] + 1) % kM;
      t -= !--c[j];
    }
    t += !c[s[i - 1]]++;
  }
  ans = (ans + g[n][k] + (t == k)) % kM;
}

int main() {
  cin >> s >> k;
  n = s.length();
  for (int i = 0; i < n; i++) {
    s[i] -= (s[i] <= '9' ? '0' : 'A' - 10);
  }
  C1(), C2();
  cout << ans;
  return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
 
const int maxl=2e5+10;
const int mod=1e9+7;
 
int n,k;
int a[maxl];
ll dp[maxl][17][2][2];
char s[maxl];
 
inline ll dfs(int pos,int st,bool up,bool lead)
{
	int cnt=__builtin_popcount(st);
	if(cnt>k) return 0;
	if(pos>n) return cnt==k;
	ll &ret=dp[pos][cnt][up][lead];
	if(ret!=-1)
		return ret;
	ret=0;
	int r=up?a[pos]:15;
	for(int i=0;i<=r;i++)
		ret=(ret+dfs(pos+1,(!i&&!lead)?st:st|(1<<i),up&&(i==r),lead|i))%mod;
	return ret;
}
 
int main()
{
	scanf("%s",s+1);scanf("%d",&k);
	n=strlen(s+1);
	for(int i=1;i<=n;i++)
	if(s[i]>='A' && s[i]<='Z')
		a[i]=s[i]-'A'+10;
	else
		a[i]=s[i]-'0';
	memset(dp,-1,sizeof(dp));
	printf("%lld\n",dfs(1,0,1,0));
	return 0;
}