#include<bits/stdc++.h>
using namespace std;
#define int long long
string s;
int n,k;
int C[18][19];
const int mod=1e9+7;
int cnt[190];
int ans=0;
char base[16]={'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};
const int N=2e5+5;
int dp[N][18][18];
int poww(int a,int b,int c){
        int ans=1,base=a;
        while(b){
                if(b&1)ans=1ll*ans*base%c;
                b>>=1;
                base=1ll*base*base%c;
        }
        return ans;
}
signed main(){
        cin>>s;
        cin>>k;
        for(int i=0;i<18;i++)dp[0][0][i]=1;
        for(int kk=0;kk<18;kk++)
        for(int i=1;i<N;i++)
                for(int j=0;j<=kk;j++){
                        dp[i][j][kk]=(dp[i-1][j][kk]*1ll*(j+k-kk)+(j>0?dp[i-1][j-1][kk]*1ll*(kk-(j-1)):0))%mod;
                }
        n=s.size();
        for(int i=0;i<18;i++)C[i][0]=1;
        for(int i=1;i<18;i++)
                for(int j=1;j<=i;j++)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
        int now=0;
        for(int i=0;i<n;i++){
                for(int j=(i==0?1:0);j<16;j++)if(base[j]<s[i]){
                        int gg=now+(cnt[base[j]]==0);
                        if(gg<=k)ans=(ans+1ll*C[16-gg][k-gg]*dp[n-(i+1)][k-gg][k-gg])%mod;
                //      cout<<i<<" "<<n-i-1<<" "<<k-gg<<" "<<dp[n-i-1][k-gg]<<endl;
                }else break;
                cnt[s[i]]++;
                if(cnt[s[i]]==1)now++;
        //      cout<<i<<" "<<ans<<endl;
        }
        if(now==k)ans++;
        //cout<<ans<<endl;
        int some=15ll*C[15][k-1]%mod;
        for(int i=1;i<n;i++){
                ans=(ans+1ll*some*dp[n-(i+1)][k-1][k-1])%mod;
        }
        cout<<ans<<endl;
        return 0;
}
# include <stdio.h>
# include <string.h>

using namespace std;

const int mod = 1000000007;
const int kMaxN = 200200;

int k, n;
char s[kMaxN];
long long a[kMaxN];
long long dp[kMaxN][20];

int Cnt(int x) {
  int cnt = 0;
  while (x) {
    cnt += x & 1;
    x >>= 1;
  }
  return cnt;
}
int main() {
  scanf("%s%d", s, &k);
  int n = strlen(s);
  for (int i = 0; i < n; i++) {
    if (s[i] >= 'A' && s[i] <= 'F') {
      a[i] = s[i] - 'A' + 10;
    } else {
      a[i] = s[i] - '0';
    }
  }
  dp[1][1] = a[0] - 1;
  long long num = 1ll << a[0];
  for (int i = 1; i < n; i++) {
    for (int j = 1; j <= 16; j++) {
      dp[i + 1][j] = (dp[i + 1][j] + dp[i][j] * j) % mod;
      dp[i + 1][j + 1] = (dp[i + 1][j + 1] + dp[i][j] * (16 - j)) % mod;
    }
    dp[i + 1][1] = (dp[i + 1][1] + 15) % mod;
    for (int j = 0; j < a[i]; j++) {
      dp[i + 1][Cnt(num | 1ll << j)] = (dp[i + 1][Cnt(num | 1ll << j)] + 1) % mod;
    }
    num |= 1ll << a[i];
  }
  if (Cnt(num) == k) {
    printf("%lld", (dp[n][k] + 1) % mod);
  } else {
    printf("%lld", dp[n][k]);
  }
}