#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define inf 1e9
#define linf 1e18
#define BASE 1000000
#define EPS 1e-10
#define PI acos(-1)
#define pii pair<int,int>
#define pdi pair<double,int>
#define vi vector<int>
#define fi first
#define se second
#define ALL(x) (x).begin(), (x).end()
#define ms(x,val_add) memset(x, val_add, sizeof(x))
#define pb(x) push_back(x)
#define make_unique(x) sort(ALL(x)) ; x.erase( unique(ALL(x)), x.end()) ;
#define dbg(x) do { cout << #x << " = " << x << endl; } while(0)
#define mp(x, y) make_pair(x, y)
#define minimize(x, y) x = min(x, y)
#define maximize(x, y) x = max(x, y)


/*** IMPLEMENTATION ***/
bool exitInput = false;
int ntest = 1, itest = 1 ;

const int dx[4] =
{
    -1, 0, 1, 0
};
const int dy[4] =
{
    0, 1, 0, -1
};

const ll Mod = 1000000007LL;
const int maxn = 200000 + 5;
const int maxv = 500 + 5;
const int maxe = 10000 + 5;

void addMod(ll &x, ll y)
{
    x = (x + y) % Mod;
}
ll modPow(ll x, ll p)
{
    if(p == 0)
        return 1;
    ll r = modPow(x, p / 2);
    r = (r * r) % Mod;
    if(p & 1)
        r = (r * x) % Mod;
    return r;
}

string s;
int n, K;
ll fact[17], choose[17][17];
ll woz[maxn][17], wz[maxn][17];
ll f[maxn][17]; // handle missing
ll res = 0;

int main()
{
    #ifdef HOME
    freopen( "input.txt", "r", stdin );
    freopen( "output.txt", "w", stdout );
    #endif // HOME
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout << setprecision(10);
    cout << fixed;

    fact[0] = 1;
    for(int i = 1; i <= 15; ++i)
        fact[i] = (fact[i-1] * i) % Mod;
    for(int i = 0; i <= 15; ++i)
        choose[i][0] = choose[i][i] = 1;
    for(int i = 1; i <= 15; ++i)
        for(int j = 1; j < i; ++j)
            choose[i][j] = (choose[i-1][j-1] + choose[i-1][j]) % Mod;

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

    // First step: count numbers with smaller length
    woz[0][0] = 1;
    for(int h = 1; h < n; ++h)
    {
        woz[h][1] = 1;
        for(int k = 2; k <= K && k <= h; ++k)
        {
            woz[h][k] = (k * (woz[h-1][k-1] + woz[h-1][k])) % Mod;
            wz[h][k] = ((k-1) * (woz[h-1][k-1] + woz[h-1][k])) % Mod;
        }
        addMod(res, choose[15][K] * woz[h][K]);
        addMod(res, choose[15][K-1] * wz[h][K]);
    }
    //cout << "first step, res = " << res << endl;
    // Second step: count numbers with equal length

    for(int h = 0; h < n; ++h)
    {
        f[h][0] = modPow(K, h);
    }
    for(int h = 1; h < n; ++h)
    {
        for(int k = 1; k <= K && k <= h; ++k)
        {
            f[h][k] = (f[h-1][k-1] * k + f[h-1][k] * (K - k)) % Mod;
        }
    }
    int cnt[16] ={0};
    for(int i = 0; i < n; ++i)
    {
        int h = n - 1 - i;
        int val = ('A' <= s[i] && s[i] <= 'Z'? s[i] - 'A' + 10 : s[i] - '0');
        int lo = (i == 0 ? 1 : 0);
        int hi = (i == n - 1 ? val : val - 1);
        for(int k = lo; k <= hi; ++k)
        {
            cnt[k]++;
            int cnt_existed = 0;
            for(int x = 0; x <= 15; ++x)
                cnt_existed += cnt[x] > 0;
            int cnt_missing = K - cnt_existed;
            if(cnt_missing >= 0)
            {
                addMod(res, choose[16 - cnt_existed][cnt_missing] * f[h][cnt_missing]);
            }
            cnt[k]--;
        }
        cnt[val]++;
    }
    cout << res << endl;

    return 0;
}


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

#define ll long long
#define all(x) x.begin(), x.end()
#define wa(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

#define int ll

const int mod = 1e9 + 7;
const int N = 2e5 + 5;
int a[N], cnt = 0;
int dp[N][20];
bool vis[20];

int mult(int x, int y){
	return ((x % mod) * (y % mod)) % mod;
}

int sum(int x, int y){
	return ((x % mod) + (y % mod)) % mod;
}


void solve(){
	string s; cin >> s;
	int k; cin >> k;
	int n = s.size();
	for(int i = 1; i <= n; ++i){
		if('0' <= s[i - 1] && s[i - 1] <= '9')
			a[i] = s[i - 1] - '0';
		else
			a[i] = s[i-1] - 'A' + 10;
	}
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= 16; ++j){
			dp[i][j + 1] = sum(dp[i][j + 1], mult(dp[i - 1][j], (16 - j)));
			dp[i][j] = sum(dp[i][j], mult(dp[i - 1][j], j));
		}
		if(i != 1) dp[i][1] = sum(dp[i][1], 15);
		for(int j = (int) (i == 1); j < a[i]; ++j){
			dp[i][cnt + !vis[j]]++;
		}
		if(!vis[a[i]]) vis[a[i]] = 1, ++cnt;
	}
	cout << ( sum(dp[n][k], (cnt == k)) % mod) << "\n";
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	int test = 1;
	while(test--) solve();
}
