#line 2 "/home/defineprogram/Desktop/Library/template/template.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for (int i = 0; i < n; i++)
#define REP(i, n) for (int i = 1; i < n; i++)
#define rev(i, n) for (int i = n - 1; i >= 0; i--)
#define REV(i, n) for (int i = n - 1; i > 0; i--)
#define all(v) v.begin(), v.end()
#define PL pair<ll, ll>
#define PI pair<int,int>
#define len(s) (int)s.size()

template <class T, class U>
inline bool chmin(T &a, U b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T, class U>
inline bool chmax(T &a, U b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
constexpr ll inf = 3e18;
#line 3 "/home/defineprogram/Desktop/Library/math/extgcd.cpp"

ll extGCD(ll a, ll b, ll &x, ll &y) {
    if (!b) {
        x = 1;
        y = 0;
        return a;
    }
    ll d = extGCD(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

ll modinv(ll a, ll m) {
    ll x, y;
    extGCD(a, m, x, y);
    return (x % m + m) % m;
}
#line 4 "/home/defineprogram/Desktop/Library/math/modint.cpp"

template <int MOD>
struct mint {
    int32_t n;
    mint() : n(0) {}
    mint(ll x) : n(x >= 0 ? x % MOD : (MOD - (-x) % MOD) % MOD) {}

    mint &operator+=(const mint &p) {
        if ((n += p.n) >= MOD) n -= MOD;
        return *this;
    }
    mint &operator-=(const mint &p) {
        if ((n += MOD - p.n) >= MOD) n -= MOD;
        return *this;
    }
    mint &operator*=(const mint &p) {
        n = 1ll * n * p.n % MOD;
        return *this;
    }
    mint &operator/=(const mint &p) {
        *this *= p.inverse();
        return *this;
    }
    mint operator-() const { return mint(-n); }
    mint operator+(const mint &p) const { return mint(*this) += p; }
    mint operator-(const mint &p) const { return mint(*this) -= p; }
    mint operator*(const mint &p) const { return mint(*this) *= p; }
    mint operator/(const mint &p) const { return mint(*this) /= p; }
    bool operator==(const mint &p) const { return n == p.n; }
    bool operator!=(const mint &p) const { return n != p.n; }

    friend ostream &operator<<(ostream &os, const mint &p) {
        return os << p.n;
    }
    friend istream &operator>>(istream &is, mint &p) {
        int x;
        is >> x;
        p = mint(x);
        return is;
    }
    mint pow(int64_t x) const {
        mint res(1), mul(n);
        while (x > 0) {
            if (x & 1) res *= mul;
            mul *= mul;
            x >>= 1;
        }
        return res;
    }
    mint inverse() const {
        return mint(modinv(n,MOD));
    }
};
/*
@brief mod int
@docs docs/modint.md
*/
#line 3 "main.cpp"
constexpr int mod=1e9+7;
using modint=mint<mod>;

string N; int K;
modint dp[1<<18][20][2];
int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    cin>>N>>K;
    dp[0][0][0]=1;
    auto f=[](char c)->int{
        if(c<='9')return c-'0';
        return c-'A'+10;
    };
    int MASK=0;
    rep(i,len(N)){
        int n=f(N[i]);

        if(i){
            REP(k,16){
                dp[i+1][1][1]+=1;
            }
        }
        rep(j,17){
            if(MASK>>n&1){
                dp[i+1][j][0]+=dp[i][j][0];
            }else{
                dp[i+1][j+1][0]+=dp[i][j][0];
            }
            rep(k,n){
                if(MASK>>k&1){
                    dp[i+1][j][1]+=dp[i][j][0];
                }else if(i||k){
                    dp[i+1][j+1][1]+=dp[i][j][0];
                }
            }
            dp[i+1][j][1]+=dp[i][j][1]*j;
            dp[i+1][j+1][1]+=dp[i][j][1]*(16-j);
        }
        MASK|=1<<n;
    }
    cout<<dp[len(N)][K][0]+dp[len(N)][K][1]<<endl;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
const int mod=1e9+7;
int n,m;
int C[17][17];
char s[N];
int a[N];
int w[200];
inline int po(int x,int k){
	int ret=1;
	while(k){
		if(k&1) ret=1ll*ret*x%mod;
		x=1ll*x*x%mod;
		k>>=1;
	}
	return ret;
}
inline int calc(int f,int c){
	if(c<m-f) return 0;
	int ret=0;
	for(int i=m;i>=f;i--){
		if(m-i&1) ret=(ret-1ll*C[m-f][i-f]*po(i,c)%mod+mod)%mod;
		else ret=(ret+1ll*C[m-f][i-f]*po(i,c))%mod;
	}
	return ret;
}
int cnt[17],tot;
int main(){
	int i,j;
	for(i='0';i<='9';i++) w[i]=i-'0';
	for(i='A';i<='F';i++) w[i]=i-'A'+10;
	for(i=0;i<17;i++){
		for(j=0;j<17;j++){
			if(j==0||j==i) C[i][j]=1;
			else C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
		}
	}
	cin>>(s+1);n=strlen(s+1);
	for(i=1;i<=n;i++) a[i]=w[s[i]];
	cin>>m;
	int ans=0;
	for(i=2;i<=n;i++){
		ans=(ans+1ll*C[15][m]*calc(0,n-i+1))%mod;
		ans=(ans+1ll*C[15][m-1]*(m-1)%mod*calc(1,n-i))%mod;
	}
	ans=(ans+1ll*C[15][m-1]*(a[1]-1)%mod*calc(1,n-1))%mod;
	for(i=1;i<n;i++){
		cnt[a[i]]++;if(cnt[a[i]]==1) tot++;
		if(tot>m) break;
		if(a[i+1]==0) continue;
		int s1=0,s2=0;
		for(j=0;j<a[i+1];j++)
			if(cnt[j]) s1++;
		s2=tot-s1;
		int t1=a[i+1]-s1,t2=16-a[i+1]-s2;
		for(j=0;j<=t1&&j<=m-tot;j++)
			ans=(ans+1ll*C[t1][j]*C[t2][m-tot-j]%mod*(1ll*s1*calc(tot,n-i-1)+1ll*j*calc(tot+1,n-i-1)))%mod;
	}
	cnt[a[n]]++;if(cnt[a[n]]==1) tot++;
	if(tot==m) ans=(ans+1)%mod;
	cout<<ans;
	return 0;
}
