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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1000 * 1000 * 1000 + 7;
const int INF = 1e9 + 100;
const ll LINF = 1e18 + 100;

#ifdef DEBUG
#define dbg(x) cout << #x << " = " << (x) << endl << flush;
#define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; }
#else
#define dbg(x) ;
#define dbgr(s, f) ;
#endif
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
//#define fast_io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//#define msub(a, b) ((mod + ((ll)(a) - (b)) % mod) % mod)
//#define mdiv(a, b) ((ll)(a) * poww((b), mod - 2) % mod)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define endl '\n'

#define MAXN 200100
#define MAXK 20

ll poww(ll a, ll b)
{
	ll res = 1;
	while (b)
	{
		if (b & 1) res = res * a % mod;
		a = a * a % mod;
		b /= 2;
	}
	return res;
}

string s;
int k;
int n;
ll ans;
ll dp[MAXK];
ll comb[MAXK][MAXK];
ll ps[MAXK];

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

ll f(int n, int k, int t)
{
	if (k - t > n) return 0;
	if (n == 0 && k == t) return 1;

	ll res = 0;
	FOR(i, 0, k - t + 1)
	{
		res = (res + comb[k - t][i] * poww(k - i, n) * (i % 2 ? -1 : 1)) % mod;
	}
	res = (res * comb[16 - t][k - t]) % mod;
	res = (mod + res) % mod;
	return res;
}

int cnt[MAXN];
int dif;

inline void add(int x)
{
	cnt[x]++;
	if (cnt[x] == 1)
		dif++;
}

inline void rem(int x)
{
	cnt[x]--;
	if (cnt[x] == 0)
		dif--;
}

int32_t main(void)
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	cin >> s >> k;
	n = s.size();

	FOR(i, 0, MAXK)
	{
		comb[i][0] = comb[i][i] = 1;
		FOR(j, 1, i)
			comb[i][j] = (comb[i - 1][j - 1] + comb[i - 1][j]) % mod;
	}

	FOR(i, 0, n)
	{
		int fr = (i ? 0 : 1);
		int d = getdig(s[i]);
		FOR(j, fr, d)
		{
			add(j);
			if (dif <= k) ans = (ans + f(n - i - 1, k, dif)) % mod;
			rem(j);
		}
		add(d);
		if (dif > k) break;
	}
	if (dif == k)
		ans = (ans + 1) % mod;

	FOR(i, 1, n)
	{
		ans = (ans + f(i - 1, k, 1) * 15) % mod;
	}

	cout << ans << endl;

	return 0;
}


#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const ll N=2e5+5;
char s[N];
ll k,len;
ll nums[N];
ll dp[N][20][2][2];

ll dfs(ll pos,int st,bool pre,bool limit){
    int cnt=__builtin_popcount(st);
    if(cnt>k) return 0;
    if(pos>len) return cnt==k&&pre;
    if(dp[pos][cnt][limit][pre]!=-1) return dp[pos][cnt][limit][pre];
    ll ans=0;
    ll up=limit?nums[pos]:15;
    for(int i=0;i<=up;i++){
        ans=(ans+dfs(pos+1,(!i&&!pre)?st:st|(1<<i),i|pre,i==up&&limit))%mod;
    }
    if(!limit) dp[pos][cnt][limit][pre]=ans;
    return ans;
}

int main(){
    memset(dp,-1,sizeof(dp));
    cin>>s+1>>k;
    len=strlen(s+1);
    for(ll i=1;i<=len;i++){
        if(s[i]>='0'&&s[i]<='9') nums[i]=s[i]-'0';
        else nums[i]=s[i]-'A'+10;
    }
    cout<<dfs(1,0,0,true)<<"\n";
}