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

#define IOS ios::sync_with_stdio(false); cin.tie(0);cout.tie(0)

const int P = 1e9 + 7;
const double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
const int N = 3e6 + 10;

int main()
{
	IOS;
	int n;
	string str;
	vector<int> v;
	cin >> str >> n;

	for(auto x : str)
		if(x >= '0' && x <= '9') v.push_back((int)(x - '0'));
		else v.push_back((int)(10 + x - 'A'));
	
	vector<vector<int> > f(str.size() + 1, vector<int>(18, 0));
	
	int state = 0;
	for(int i = 0; i < (int)str.size(); ++ i)
	{
		for(int j = 1; j <= 16; ++ j)
		{
			f[i + 1][j] = (f[i + 1][j] + (LL)f[i][j] * j % P) % P;
			f[i + 1][j + 1] = (f[i + 1][j + 1] + (LL)f[i][j] * (16 - j) % P) % P;
		}
		f[i + 1][1] = (f[i + 1][1] + (LL)f[i][0] * 15 % P) % P;
		f[i + 1][0] = (f[i + 1][0] + f[i][0]) % P;
		for(int j = 0; j < v[i]; ++ j)
		{
			int nstate = state;
			if(i || j) nstate |= (1 << j);
			f[i + 1][__builtin_popcount(nstate)] += 1;
		}
		state |= (1 << v[i]);
	}

	int res = f[str.size()][n] + (__builtin_popcount(state) == n);
	cout << res << endl;
	
	return 0;
} 
#include <cstdio>
#include <iostream> 
using namespace std;
typedef long long LL;
const int mod = 1e9 + 7;
const int L = 2e5 + 100;
const int K = 16 + 4;

char lmt[L]; int lp;
long long f[L][K];
bool has[L]; int cnt;

int n, k;

int main() {
	char in = getchar();
	while((in < '0' || in > '9') && (in < 'A' || in > 'F')) in = getchar();
	while((in >= '0' && in <= '9') || (in >= 'A' && in <= 'F')) {
		lmt[++lp] = (in < 'A') ? (in - '0') : (in - 'A' + 10);
		in = getchar();
	}
	scanf("%d", &k);
		f[1][1] = max(0, lmt[1] - 1);
		for(int i = 2; i <= lp; ++i)
			f[i][1] = 15;
		
		for(int i = 1; i <= lp; ++i) {
			if(!has[lmt[i]]) ++cnt;
			has[lmt[i]] = true;
			for(int j = 01; j <= 16; ++j) {
				f[i + 1][j] += f[i][j] * j;
				f[i + 1][j] %= mod;
				f[i + 1][j + 1] += f[i][j] * (16 - j);
				f[i + 1][j + 1] %= mod;
			}
			for(int k = 0; k < lmt[i + 1]; ++k) {
				f[i + 1][cnt] += has[k];
				f[i + 1][cnt] %= mod;
				f[i + 1][cnt + 1] += !has[k];
				f[i + 1][cnt + 1] %= mod;
			}
		}
	cout << (f[lp][k] + (cnt == k)) % mod;
	return 0;
}