#include <bits/stdc++.h>
using namespace std;

#define fr(i,n) for(int i = 0; i<n; i++)
#define sz(v) (int)(v.size())
#define prin(a) cout << #a << " = " << a << endl
#define prinv(v) cout << #v << " = "; for(auto it : v) cout << it << ", "; cout << endl
#define all(v) (v).begin(),(v).end()

typedef long long ll;

#define rmin(a,b) a = min<ll>(a,b)
#define rmax(a,b) a = max<ll>(a,b)

#define fi first
#define se second

template <class T>
T fp(T x, long long e) {
	T ans(1);
	for(; e > 0; e /= 2) {
		if(e & 1) ans = ans * x;
		x = x * x;
	}
	return ans;
}

const ll mod = round(1e9)+7;
struct mb {
	mb(int v = 0) : val(v < 0 ? v + mod : v) {}
	mb(ll v){ val = (v%mod+mod)%mod; }
	int val;
 
	void operator += (mb o) { *this = *this + o; }
	void operator -= (mb o) { *this = *this - o; }
	void operator *= (mb o) { *this = *this * o; }
	mb operator * (mb o) { return (int)((long long) val * o.val % mod); }
	mb operator / (mb o) { return *this * fp(o, mod - 2); }
	//bool operator == (mb o) { return val==o.val; } //usar soh para hashes
	mb operator + (mb o) { return val + o.val >= mod ? val + o.val - mod : val + o.val; }
	mb operator - (mb o) { return val - o.val < 0 ? val - o.val + mod : val - o.val; }
};

const int NFAT = 20;
mb fat[NFAT], invfat[NFAT];

mb nck(int n, int k){
	assert(n>=k);
	return fat[n]*invfat[k]*invfat[n-k];
}

const int N = 2e5+10;

int v[N];
mb pot[20][N];

int n;
int va[N];
ll ans_brute = 0;
ll K; 

bool check(){
	ll soma = 0;
	fr(i,n) soma+=va[i];
	if(!soma) return 0;
	fr(i,n){
		if(va[i]!=v[i]){
			if(va[i]<v[i]) break;
			return 0;
		}
	}
	set<int> st;
	int i = 0;
	while(i<n and va[i]==0) i++;
	for(;i<n; i++) st.insert(va[i]);
	
	return sz(st)==K;
	
}

void go(int i){
	if(i==n){
		if(check()) ans_brute++;
		return;
	}
	int minv = 16;
	if(i==0) minv = v[i]+1;
	fr(val,minv){
		va[i] = val;
		go(i+1);
	}
}



int ton(char c){
	if(c>='0' and c<='9') return c-'0';
	return 10+c-'A';
}

int vis[20][20][N];
mb dp[20][20][N];

mb rec(int ja_usei, int need_usar, int n){
	int delt = need_usar-ja_usei;
	if(delt>n) return 0;
	if(n==0) return delt==0;
	mb &ans = dp[ja_usei][need_usar][n];
	if(vis[ja_usei][need_usar][n]) return ans;
	vis[ja_usei][need_usar][n] = 1;
	if(ja_usei) ans += rec(ja_usei,need_usar,n-1)*ja_usei;
	if(ja_usei<need_usar) ans += rec(ja_usei+1,need_usar,n-1)*(need_usar-ja_usei);
	return ans;
}

mb ways_use(ll k, ll n){
	return rec(0,k,n);
	assert(vis[0][k][n]);
	return dp[0][k][n];
	if(k==0){
		if(n==0) return 1;
		return 0;
	}
	if(k>n) return 0;
	assert(k>=1 and k<=16);
	return pot[k][n]-pot[k-1][n]*k;
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	fat[0] = invfat[0] = mb(1);
	for(int i = 1; i<NFAT; i++){
		fat[i] = mb(i)*fat[i-1];
		invfat[i] = mb(1)/fat[i]; //fp(fat[i],MOD-2);
	}
	
	for(ll val = 1; val<=16; val++){
		pot[val][0] = 1;
		for(int i = 1; i<N; i++) pot[val][i] = pot[val][i-1]*val;
	}
	
	string s; cin >> s;
	cin >> K;
	n = sz(s);
	//prin(n);
	
	fr(i,sz(s)) v[i] = ton(s[i]);
	
	mb ans = 0;
	
	vector<int> freq(16);
	int ndif = 0;
	mb aux = 0;
	fr(i,n){
		//prin(i);
		//prin(v[i]);
		mb cur = 0;
		fr(val,16){
			if(val==0 and i==0) continue;
			if(val>=v[i]) break;
			ll nrest = n-i-1;
			int curdif = ndif;
			if(!freq[val]) curdif++;
			if(curdif>K) continue;
			//prin(val);
			ll need_add = K-curdif;
			for(ll add = need_add; add<=K; add++){
				ans +=  nck(16-curdif,need_add)*nck(curdif,add-need_add)*ways_use(add,nrest);
			}
			//return 0;
		}
		//prin(cur.val);
		//prin(ans.val);
		freq[v[i]]++;
		if(freq[v[i]]==1) ndif++;
		if(ndif>K) break;
	}
	//prin(aux.val);
	if(ndif==K) ans += 1;
	if(n>=2){ 
		for(int i = 1; i<n; i++){
			fr(val,16){
				if(val==0) continue;
				ll nrest = n-i-1;
				int curdif = 1;
				if(curdif>K) continue;
				ll need_add = K-curdif;
				for(ll add = max<ll>(0,need_add); add<=K; add++){
					ans += nck(16-curdif,need_add)*nck(curdif,add-need_add)*ways_use(add,nrest);
				}
			}
		}
	}
	//prin(ans.val);
	
	cout << ans.val << "\n";
}
#include<bits/stdc++.h>
#define int long long
#define double long double
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define x first
#define y second
using namespace std;
using pi = pair<int,int>;
const int inf = 0x3f3f3f3f3f3f3f3f;
const int minf = 0xc0c0c0c0c0c0c0c0;
const int mod = 1e9+7;

int A[200200];
int dp[200200][20];

int c2i(char c) {
    if (c >= '0' && c <= '9') return c-'0';
    return c-'A'+10;
}

void add(int &ref, int val) {
    ref = (ref+val)%mod;
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cout<<fixed<<setprecision(10);
    string s; int k; cin>>s>>k;
    int n = sz(s);
    for (int i=0; i<n; i++) {
        A[i] = c2i(s[i]);
    }
    dp[0][1] = A[0] - 1;
    int bit = 1<<A[0];
    for (int i=1; i<n; i++) {
        for (int j=1; j<=16; j++) {
            add(dp[i][j], dp[i-1][j]*j);
            add(dp[i][j+1], dp[i-1][j]*(16-j));
        }
        add(dp[i][1], 15);
        for (int j=0; j<A[i]; j++) {
            add(dp[i][__builtin_popcountll(bit|(1<<j))], 1);
        }
        bit |= 1<<A[i];
    }
    if (__builtin_popcountll(bit) == k) add(dp[n-1][k], 1);
    cout<<dp[n-1][k]<<'\n';
    return 0;
}