#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MOD = 1e9+7;
const int MAXN = 2e5 + 7;
int k;
ll dp[MAXN][17];
// dp[i][j] = number of possibilities up to digit i
//smaller than n, nonzero, with j distinct digits
string n;
map<char,int> mp;
int mask = 0;

int main(){
    for(char c='0'; c<='9'; c++)mp[c] = c-'0';
    for(char c='A'; c<='F'; c++)mp[c] = 10 + c-'A';

    cin >> n >> k;

    for(int i=0; i < (int)n.size(); i++){

        int aux = mp[n[i]];//current digit

        if(i > 0){
            //possibilities that were smaller before
            for(int j=1; j<=16; j++){//just add any digit
                dp[i][j] = (dp[i][j] + j*dp[i-1][j])%MOD;//already j
                dp[i][j] = (dp[i][j] + (17-j)*dp[i-1][j-1])%MOD;//was j-1, add new
            }

            //possibilities that become smaller now
            for(int digit=0; digit < aux; digit++){
                if( mask == (mask|(1<<digit)) ){//repeated
                    dp[i][__builtin_popcount(mask)] = (dp[i][__builtin_popcount(mask)] + 1)%MOD;
                }else{
                    dp[i][__builtin_popcount(mask) + 1] = (dp[i][__builtin_popcount(mask) + 1] + 1)%MOD;
                }
            }
        }
        //first nonzero digit
        if(i > 0)dp[i][1] = (dp[i][1] + 15)%MOD;
        else dp[i][1] = (dp[i][1] + aux - 1)%MOD;

        mask |= (1<<aux);
    }

    int acc = 0;
    if(__builtin_popcount(mask) == k)acc = 1;//n inclusive

    cout<<(dp[(int)n.size()-1][k]  + acc)%MOD<<endl;
}
#include <iostream>
#include <vector>
 
#define rep(i,n) for(int i=0;i<(int)(n); i++)
 
using namespace std;
using ll = long long;
 
const ll mod = 1e9+7;
const int N_MAX = 2e5+1;
const int K_MAX = 17;
 
ll dp[N_MAX][K_MAX][2];
 
int main()
{
    string S; cin>>S;
    int N = S.size();
    int K; cin>>K;
    vector<int> nums(N);
    rep(i,N) nums[i]=('0'<=S[i]&&S[i]<='9')?(S[i]-'0'):(S[i]-'A'+10);
 
    vector<int> mask(N+1);
    vector<int> popcnt(N);
    rep(i,N){
        mask[i+1] = mask[i]|1<<nums[i];
        popcnt[i]=__builtin_popcount(mask[i+1]);
    }
 
    dp[0][0][0] = 1;
    rep(i,N)rep(j,K_MAX){
        // same
        (dp[i+1][popcnt[i]][0]+=dp[i][j][0])%=mod;
        rep(d,nums[i]){
            if (j==0 && d==0){
                (dp[i+1][0][1]+=dp[i][0][0])%=mod;
                continue;
            }
            int nj = j + ((mask[i]>>d&1)?0:1);
            (dp[i+1][nj][1]+=dp[i][j][0])%=mod;
        }
        // lower
        if (j==0){
            (dp[i+1][0][1]+=dp[i][0][1])%=mod;
            (dp[i+1][1][1]+=dp[i][0][1]*15)%=mod;
        }else{
            (dp[i+1][j][1]+=dp[i][j][1]*j)%=mod;
            if (j+1<=16) (dp[i+1][j+1][1]+=dp[i][j][1]*(16-j))%=mod;
        }
    }
    cout<<dp[N][K][0]+dp[N][K][1]<<"\n";
    return 0;
}