#include <bits/stdc++.h>          
using namespace std;
using ll = long long;
using ld = long double;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repp(i, st, en) for (ll i = (ll)st; i < (ll)(en); i++)
#define repm(i, st, en) for (ll i = (ll)st; i >= (ll)(en); i--)
#define all(v) v.begin(), v.end()
void chmax(ll &x, ll y) {x = max(x,y);}
void chmin(ll &x, ll y) {x = min(x,y);}
void Yes() {cout << "Yes" << endl; exit(0);}
void No() {cout << "No" << endl; exit(0);}
template<class in_Cout> void Cout(in_Cout x) {cout << x << endl; exit(0);}
template<class in_vec_cout>
void vec_cout(vector<in_vec_cout> vec) {
    for (in_vec_cout res : vec) {cout << res << " ";}
    cout << endl;
}

const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll d = 16;

ll dp[220000][2][17];

ll to_num(char c) {
    ll x = c - '0';
    if (0<=x && x<10) return x;
    ll y = c - 'A';
    return 10 + y;
}

ll bitcnt(ll bit) {
    ll res = 0;
    rep(i,d) if ((bit>>i)&1) res++;
    return res;
}

void addmodp(ll &x, ll y) {x = (x + y) % mod;}

int main() {
    string str; cin >> str;
    ll N = str.size();
    ll K; cin >> K;
    vector<ll> S(N);
    rep(i,N) S[i] = to_num(str[i]);

    ll bit = 1<<S[0];
    dp[0][0][1] = 1LL;
    dp[0][1][1] = S[0] - 1;
    for (ll i=1; i<N; i++) {
        ll from = bitcnt(bit);
        bit |= 1<<S[i];
        ll now = bitcnt(bit);
        dp[i][0][now] = 1;
        for (ll j=1; j<=d; j++) {
            addmodp(dp[i][1][j], dp[i-1][1][j] * j % mod);
            addmodp(dp[i][1][j], dp[i-1][1][j-1] * (d-j+1) % mod);
        }
        rep(j,S[i]) {
            if ((bit>>j)&1) addmodp(dp[i][1][from],1LL);
            else addmodp(dp[i][1][from+1],1LL);
        }
        addmodp(dp[i][1][1],15);
    }

    ll ans = 0LL;
    rep(i,2) addmodp(ans,dp[N-1][i][K]);
    Cout(ans);
}
#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();
}
