#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
char s[200100];
ll N, pw[17][200100], a[200100], C[17][17]; const ll mod = 1e9+7;
ll D[20][20][200100], D2[20][20][200100];
ll f(ll n){
    ll i, j, cnt = 0, ret = 0;
    set <ll> S;
    if(n == 0) return -1;
    for(i=1; i<=N; i++) {
        for(j=0; j<a[i]; j++) {
            if(i == 1 && j == 0) continue;
            ll now, flag = 0;
            if(S.find(j) == S.end()) { cnt++; flag = 1; }
//            now = n-cnt;
//            ret -= pw[cnt][N-i] * (C[16-cnt][now] - 1); ret %= mod;
//            ret += pw[n][N-i] * C[16-cnt][now]; ret %= mod;
//            ret += mod; ret %= mod;
            ret += D[cnt][n][N-i]; ret %= mod;
            if(flag) cnt--;
        }
        if(S.find(a[i]) == S.end()) {
            cnt++; S.insert(a[i]);
            if(cnt > n) break;
        }
    }
    if(i == N+1) ret++;
    for(i=2; i<=N; i++) {
        ret += D2[0][n][N-i+1];
    }
    ret--; ret %= mod;
    return ret;
}

int main(){
    //ios_base::sync_with_stdio(false); cin.tie(0);
    ll i, j, k, K;
    scanf("%s", s+1); cin>>K; N = strlen(s+1);
    for(i=0; i<=16; i++) pw[i][0] = 1;
    for(i=1; i<=N; i++) for(j=0; j<=16; j++) {
        pw[j][i] = pw[j][i-1] * j; pw[j][i] %= mod;
    }
    for(i=1; i<=16; i++) {
        for(j=0; j<=i; j++) {
            if(j == 0 || j == i) C[i][j] = 1;
            else C[i][j] = C[i-1][j-1] + C[i-1][j];
        }
    }
    for(k=0; k<=N; k++) {
        for(i=0; i<=16; i++) {
            for(j=i; j<=16; j++) {
                if(k == 0){ D[i][j][k] = D2[i][j][k] = 1; continue; }
                D[i][j][k] = i * D[i][j][k-1] + (16-i) * D[i+1][j][k-1];
                D[i][j][k] %= mod;
                if(i == 0) D2[i][j][k] = i * D2[i][j][k-1] + (15-i) * D2[i+1][j][k-1];
                else D2[i][j][k] = i * D2[i][j][k-1] + (16-i) * D2[i+1][j][k-1];
                D2[i][j][k] %= mod;
            }
        }
    }
    for(i=1; i<=N; i++) {
        if(s[i] >= 'A' && s[i] <= 'F') a[i] = s[i] - 'A' + 10;
        else a[i] = s[i] - '0';
    }
    cout<< ( ( f(K) - f(K-1) ) % mod + mod ) % mod;
}

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
static const ll mod=1000000007;
string S;
ll K;
ll comb[17][17];
ll Pow[17][250001];
void init(){
for(ll n=0;n<17;n++)comb[n][0]=1;
  for(ll n=1;n<17;n++)
    for(ll k=1;k<=n;k++)
      comb[n][k]=(n*comb[n-1][k-1])/k;
  for(ll i=0;i<17;i++)Pow[i][0]=1;
  for(ll k=1;k<250001;k++)
    for(ll n=1;n<17;n++){
    Pow[n][k]=(Pow[n][k-1]*n)%mod;
    }
}
ll Combb(ll y,ll N){
ll sum=0;
  for(ll i=0;i<K;i++){
  ll x=(Pow[K-i][N]*comb[y][i])%mod;
    if(i%2==0)sum=(sum+x)%mod;
    else sum=(sum-x+mod)%mod;
  }
return sum;
}

int main(){
  cin>>S>>K;ll N=S.size();init();
  ll ans=0;
  for(ll n=1;n<N;n++){
  ans=(ans+Combb(K-1,n-1)*15)%mod;
  }ans=(ans*comb[15][K-1])%mod;
  set<ll>SS;
  for(ll i=0;i<N;i++){
  ll a=S[i]-'0';
    if(!(0<=a&&a<=9))
      a=S[i]-'A'+10;
    ll Y=SS.size();
    for(ll j=0;j<a;j++){
      if(i==0 && j==0)continue;
    ll y=Y;if(!SS.count(j))y++;
      if(K<y)continue;
      y=K-y;
      ll x=Combb(y,N-1-i);
      ans=(ans+comb[16-K+y][y]*x)%mod;
      
    } SS.insert(a);
  }if(SS.size()==K)ans++;
  cout<<ans<<endl;
  return 0;
}