#include <bits/stdc++.h>
using namespace std;
#define int long long
const int nax=2e5+100,mod=1e9+7;
int dp[nax][19];
int32_t main()
{
    int t=1;
    //cin>>t;
    while(t--)
    {
        string a;
        cin>>a;
        int k;
        cin>>k;
        set<int> s;
        s.clear();
        for(int i=0;i<a.size();i++)
        {
            for(int j=0;j<17;j++)
            {
                dp[i+1][j]+=dp[i][j]*j;
                dp[i+1][j]%=mod;
                dp[i+1][j+1]+=dp[i][j]*(16-j);
                dp[i+1][j+1]%=mod;
            }
            int num=a[i]-'0';
            if(a[i]>='A')
            num=10+a[i]-'A';
            for(int j=0;j<num;j++)
            {
                if(i==0 and j==0)
                continue;
                if(s.count(j))
                {
                    dp[i+1][s.size()]++;
                    dp[i+1][s.size()]%=mod;
                }
                else
                {
                    dp[i+1][s.size()+1]++;
                    dp[i+1][s.size()+1]%=mod;
                }
            }
            s.insert(num);
            if(i!=0)
            dp[i+1][1]+=15;
        }
        int res=dp[a.size()][k];
        set<char> ss;
        for(int i=0;i<a.size();i++)
        ss.insert(a[i]);
        if(ss.size()==k)
        ++res;
        cout<<res;
    }
    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);
}