#include <bits/stdc++.h>
#define int long long
#define MOD 1000000007
using namespace std;

vector<vector<int>> binoms(17,vector<int>(17,-1));

int binom(int n, int r){
    if(binoms[n][r] != -1) return binoms[n][r];
    int ans = 1;
    for(int i = 0; i < r; i ++){
        ans *= n-i;
        ans /= i+1;
    }
    return binoms[n][r] = ans;
}

int powmod(int a, int n){
    if(n == 0) return 1;
    int s = powmod(a,n/2);
    s = (s*s) % MOD;
    if(n % 2) return (a*s) % MOD;
    else return s;
}

int scent(int a, int k, int n){ //n digits, a already used
    if(n == 0) return (a == k ? 1 : 0);
    if(a > k) return 0;
    int ans = 0;
    int sign = 1;
    for(int j = k; j >= a; j --){
        ans = (ans + (sign*binom(k-a,j-a)*powmod(j,n)) % MOD + MOD) % MOD;
        sign *= -1;
    }
    return ans*binom(16-a,k-a) % MOD;
}

signed main(){
    string n; int k; cin >> n >> k;
    int s = n.size();
    vector<int> N(s); for(int i = 0; i < s; i ++) N[i] = (n[i] <= '9' ? n[i] - '0' : n[i] - 'A' + 10);
    int ans = 0;
    for(int i = 1; i < s; i ++){
        ans = (ans + 15*scent(1,k,i-1)) % MOD;
        //cout << scent(1,k,i-1) << " " << 1 << " " << k << " " << i-1 << "\n";
    }
    vector<bool> digs(16);
    int counter = 0;
    for(int i = 0; i < s; i ++){
        for(int j = 0; j < N[i]; j ++){
            if(i == 0 && j == 0) continue;
            int curcounter = counter;
            if(!digs[j]) curcounter ++;
            ans = (ans + scent(curcounter,k,s-i-1)) % MOD;
            //cout << scent(curcounter,k,s-i-1) << " " << curcounter << " " << k << " " << s-i-1 << "\n";
        }
        if(!digs[N[i]]) counter ++;
        digs[N[i]] = true;
    }
    if(counter == k) ans ++;
    cout << ans;
}
//in the name of god//
// SOBHET BEKHEIR JOOOOOOON E DEL

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define  mem(x,s)	memset(x,s,sizeof(x))
#define all(x)	x.begin(),x.end()
#define _ ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);
#define F first
#define S second
#define endi return cout<<'\n',0
#define MP make_pair
#define pb push_back
#define ppb pop_back
#define pii pair<int,int>
#define pll pair<ll,ll>
const int maxn = 1e5 + 10;
const int maxn1 = 1e3 + 10;
const ll inf = 1e18;
map <ll,ll> dp;
ll f(ll a, ll b){
    if(a >= b)
        return a - b;

    if(dp.count(b))
		return dp[b];

    else{
        ll tmp = b - a;
        if(b & 1)
            tmp = min (tmp, min(f(a, (b + 1ll) / 2ll), f(a, (b - 1ll) / 2ll)) + 2ll);

        else
           tmp = min (tmp, f(a, b / 2) + 1);

        return dp[b] = tmp;
    }
}
int main(){
    ll x, y;
    cin >> x >> y;
    cout << f(x, y) << '\n';
	return 0;
}
