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

#define int long long
#define MS(x) memset((x), -1, sizeof((x))) 
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
#define MOD 1000000007 

int k;
string s;

int memo[200010][17][17];

int dp(int i, int j, int k){
	if(i == 0){
		return j == 0 ? 1 : 0;
	}
	if(~memo[i][j][k]) return memo[i][j][k];

	int ans = 0;
	if(j > 0){
		ans += dp(i-1, j-1, k)*(16-(k+j-1)) % MOD; 
	}
	ans += dp(i-1, j, k)*(j+k) % MOD; 
	return memo[i][j][k] = ans%MOD;
}

signed main(){
	cin >> s >> k;
	int n = s.size();

	int used[512] = {};
	int cnt = 0;
	int ans = 0;

	string moji = "0123456789ABCDEF";

	MS(memo);

	for(int i = 0;i < n;i++){
		int tmp = 0; 
		int j;
		for(j = 0;moji[j] != s[i];j++){
			tmp += used[moji[j]];
		}
		int rnum = n-i-1; 
		if(i > 0){
			ans += dp(rnum, k-1, 1)*15%MOD;
			ans %= MOD;
		}
		if(j != 0){
			if(tmp != j && cnt+1 <= k){
				if(i == 0){
					ans += dp(rnum, k-1, 1)*(j-1)%MOD;
				}else{
					ans += dp(rnum, k-(cnt+1), cnt+1)*(j-tmp)%MOD;
				}
				ans %= MOD;
			}
			if(cnt > 0 && cnt <= k){
				ans += dp(rnum, k-cnt, cnt)*tmp % MOD;
				ans %= MOD;
			}
		}
		if(used[s[i]] == 0){
			used[s[i]] = 1;
			cnt++;
		}
	}

	if(cnt == k) ans = (ans+1) % MOD;

	cout << ans << endl;

	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
typedef long long ll;
string num;
int rn[200005];
int k;
int n;
int dp[200005][20];
ll dfs(int x,ll now,bool zero,bool flag)
{
    int cnt=0;
    for(int i=0;i<16;i++)
    {
        if(now&(1<<i))cnt++;
    }
    if(x>=n)return cnt==k;
    if(cnt>k)return 0;
    if(!flag&&zero&&dp[x][cnt]!=-1)return dp[x][cnt];
    ll ans=0;
    int lim=flag?rn[x]:15;
    for(int i=0;i<=lim;i++)
    {
        int tmp;
        if(!zero&&i==0)tmp=now;
        else tmp=now|(1<<i);
        ans+=dfs(x+1,tmp,zero||(i!=0),flag&&(i==lim));
        ans%=mod;
    }
    if(!flag&&zero)dp[x][cnt]=ans;
    return ans;
}
int main()
{
    cin>>num>>k;
    n=num.size();
    memset(dp,-1,sizeof dp);
    for(int i=0;i<n;i++)
    {
        if(num[i]>='0'&&num[i]<='9')rn[i]=num[i]-'0';
        else rn[i]=num[i]-'A'+10;
    }
    printf("%lld\n",dfs(0,0,0,1));
    return 0;
}
