#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 7;
typedef long long ll;
const ll mod = 1e9 + 7;
string s;
int k, a[N], n;

int work(int x) {
    int ans = 0;
    while (x) {
        if (x & 1) ans++;
        x = x / 2;
    }
    return ans;
}

ll dp[N][20];

ll dfs(int p, int stat, int limit) {
    int cnt = work(stat);
   // cout << p << " " << cnt << " " << stat  << endl;
    if (cnt > k) return 0;
    if (p == n) {
        if (cnt == k) return 1;
        return 0;
    }
    if (!limit && dp[p][cnt] != -1) return dp[p][cnt];
    int maxn = 15;
    if (limit) {
        maxn = a[p];
    }
    ll ans = 0;
    for (int i = 0; i <= maxn; i++) {
        ans += dfs(p + 1, stat | (1 << i), limit && i == maxn);
        ans = ans % mod;
    }
    if (!limit) dp[p][cnt] = ans;
    return ans;

}

void solve() {
    ll ans = 0;
    memset(dp, -1, sizeof(dp));
    for (int i = 0; i < n; i++) {
        int maxn = 15;
        if (i == 0) {
            maxn = a[0];
        }
      //  cout << "Maxn " << maxn << endl;
        for (int j = 1; j <= maxn; j++) {

            ans += dfs(i + 1, (1 << j), i == 0 && j == maxn);
            ans = ans % mod;
        }
    }
    cout << ans << endl;
}

int main() {
    cin >> s >> k;
    n = s.length();
    for (int i = 0; i < s.length(); i++) {
        if (s[i] >= '0' && s[i] <= '9') {
            a[i] = s[i] - '0';
        } else {
            a[i] = s[i] - 'A' + 10;
        }
    }
    solve();
}

#include <cstdio>
#include <cstring>
#define ll long long
using namespace std;
const ll mod=1e9+7;
ll f[200010][17][2][2],ans;int k,n,a[200010];
char s[200010];
int num(int x)
{
    if(s[x]<='9'&&s[x]>='0') return s[x]-'0';
    return s[x]-'A'+10;
}
ll dfs(int pos,int st,int maxx,bool zero)
{
    int cnt=__builtin_popcount(st);
    if(pos>n) return cnt==k;
    if(cnt>k) return 0ll;
    if(pos>n) return cnt==k&&!zero;
    if(f[pos][cnt][maxx][zero]!=-1) return f[pos][cnt][maxx][zero];
    int to=maxx?a[pos]:15;
    ll ans=0;
    for(int i=0;i<=to;i++)
        if(!i&&zero) ans=(ans+dfs(pos+1,0,0,1))%mod;
        else ans=(ans+dfs(pos+1,st|(1<<i),maxx&&i==to,0))%mod;
    f[pos][cnt][maxx][zero]=ans;
    return ans;
}
int main()
{
    scanf("%s %d",s+1,&k);
    n=strlen(s+1);
    for(int i=1;i<=n;i++)
        a[i]=num(i);
    memset(f,-1,sizeof(f));
    printf("%lld",dfs(1,0,1,1));
}