#include <iostream>
#include <bits/stdc++.h>
#define For(i,x,y) for(int i = (x);  i <= (y); i ++ )
#define fori(i,x,y) for(int i = (x); i < (y); i ++ )
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define endl '\n'
#define all(x) a.begin(), a.end()
#define mst(x,a) memset(x, a, sizeof x)
#define debug(a) cout<< #a <<": " << a << endl
using namespace std;

typedef long long LL;
typedef pair<int,int>pa;

const int inf = 0x3f3f3f3f;
const int INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9+7;
const int maxn = 2e5+10;
const int maxm = 1e6+10;
const int N = 1e6+10;

int dp[maxn][20][2][2];
int a[maxn], n, k;
int dfs(int x, int sta, bool lead = true, bool limit = true){
    int cnt = __builtin_popcount(sta);
    int& ans  = dp[x][cnt][lead][limit];
    if(~ans) return ans;
    if(cnt > k) return ans = 0;
    if(x==n) return cnt==k;
    int up = limit?a[x]:15;
    ans = 0;
    For(i,0,up){
        int add = dfs(x+1, (lead&&!i) ? sta : sta|1<<i, !i&&lead, limit && i == up);
        ans = (LL)ans + add;
        if(ans >= mod) ans -= mod;
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(0);
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
#endif
    string s;
    cin>>s>>k;
    mst(dp,-1);
    n = sz(s);
    fori(i,0,n)a[i] = isdigit(s[i])?s[i]-'0':s[i]-'A'+10;
    printf("%d\n", dfs(0,0));
    return 0;
}

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
#include<cstring>
#include<map>
#include<set>
#include<cstdlib>
#include<bitset>
using namespace std;
#define FAST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
typedef long long ll;
#define N 200005
ll p=1e9+7;
ll n,m,f[N][17][17]={0},v[22]={0},sm;
char a[N];
int main()
{
	ll i,j,k,a1,a2,an=0;
	scanf("%s",a+1);
	n=strlen(a+1);
	for(ll i=1;i<=n;i++)
		if(a[i]>='0'&&a[i]<='9')
			a[i]-='0';
		else
			a[i]-='A'-10;
	scanf("%lld",&m);
	for(ll i=0;i<=m;i++)
		f[0][i][i]=1;
	for(ll i=1;i<=n;i++)
		for(ll j=1;j<=m;j++)
			for(ll k=j;k<=m;k++)
				f[i][j][k]=((ll)f[i-1][j][k-1]*(17ll-k)+(ll)f[i-1][j][k]*k)%p;
	for(ll i=1;i<=n;i++)
		an=(an+15ll*f[i-1][1][m])%p;
	// for(ll i=1;i<=n;i++)
	// {
	// 	for(ll j=1;j<=m;j++)
	// 		for(ll k=j;k<=m;k++)printf("%lld\n",f[i][j][1]);
	// }
	for(ll i=1;i<=n;i++)
	{
		for(ll j=a[i]+1;j<=15;j++)
			an=(an-f[n-i][sm+(!v[j])][m]+p)%p;
		//printf("%lld\n",an);
		sm+=!v[a[i]];
		v[a[i]]=1;
	}
	printf("%lld",an);
}