#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
 
const int MOD = 1000000007;
vector<long long> fac, finv, inv;
 
void InitializeCombination(int COMMAX){
    fac.push_back(1LL);
    fac.push_back(1LL);
    finv.push_back(1LL);
    finv.push_back(1LL);
    inv.push_back(0LL); //Though 0^(-1) cannot be defined, there should be some number in inv[0]
    inv.push_back(1LL);
    for (int i = 2; i <= COMMAX; i++){
        fac.push_back(fac[i-1] * (long long)i % (long long)MOD);
        inv.push_back((long long)MOD - inv[MOD%i] * (long long)(MOD/i) % (long long)MOD);
        finv.push_back(finv[i-1] * inv[i] % (long long)MOD);
    }
}
 
long long Combination(int n, int r){
    if (n < r) return 0LL;
    if (n < 0 || r < 0) return 0LL;
    return fac[n] * (finv[r] * finv[n-r] % MOD) % MOD;
}
 
long long InvCombination(int n, int r){
    if (n < r) return 0LL;
    if (n < 0 || r < 0) return 0LL;
    return finv[n] * (fac[r] * fac[n-r] % MOD) % MOD;
}

int HexCharToInt(char C){
    if((C>='0')&&(C<='9'))return C-'0';
    return C-'A'+10;
}

int main(void){
    string strN;
    int K;
    long long res = 0LL;
    cin >> strN >> K;
    vector<vector<long long>> numHex(1, vector<long long>(K+1, 0LL));
    int lenN = (int)strN.size();
    InitializeCombination(16);
    numHex.push_back({});
    for(int i=0; i<=K; i++)numHex[1].push_back(i == 1 ? 16LL : 0LL);
    for(int i=2; i<=lenN; i++){
        numHex.push_back({});
        for(int j=0; j<=K; j++){
            if((j==0)||(j>i)){
                numHex[i].push_back(0LL);
            }else{
                numHex[i].push_back((numHex[i-1][j]*j%MOD+numHex[i-1][j-1]*(17-j)%MOD)%MOD);
            }
        }
    }
    for(int i=1; i<lenN; i++){
        res += numHex[i][K]*15%MOD*inv[16]%MOD;
        res %= MOD;
    }
    set<int> setSpecies;
    int numSpecies = 0;
    for(int i=0; i<lenN; i++){
        int Ni = HexCharToInt(strN[i]);
        for(int j=0; j<Ni; j++){
            if((i==0)&&(j==0))continue;
            set<int> nxtSpecies = setSpecies;
            nxtSpecies.insert(j);
            int nxtNum = (int)nxtSpecies.size();
            if(nxtNum > K)continue;
            if(i<lenN-1){
                for(int k=K-nxtNum; k<=K; k++){
                    res += numHex[lenN-i-1][k]*Combination(nxtNum, nxtNum+k-K)%MOD*Combination(16-nxtNum, K-nxtNum)%MOD*InvCombination(16, k)%MOD;
                    res %= MOD;
                }
            }else{
                if(nxtNum==K){
                    res++;
                    res %= MOD;
                }
            }
        }
        setSpecies.insert(Ni);
        numSpecies = (int)setSpecies.size();
        if(numSpecies > K)break;
    }
    if(numSpecies == K)res = (res + 1) % MOD;
    cout << res << endl;
    return 0;
}
#pragma GCC optimize("Ofast")
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

using namespace std;
#define rep(i, n) for (ll i = 0; i < (ll)(n); (i)++)
#define per(i, n) for (ll i = n - 1; i >= 0; (i)--)
#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define ROF(i, a, b) for (ll i = (b) - 1; i >= (a); i--)
#define ALL(x) std::begin(x), std::end(x)

typedef long long ll;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    //input, initialize
    int N, M; cin >> N >> M;
    vector<int> A(N);
    rep(i, N) cin >> A[i];
    //solve
    vector<vector<int>> C(M);
    rep(i, M) C[i].emplace_back(0);
    rep(i, N){
        if(A[i] >= M) continue;
        C[A[i]].emplace_back(i+1);
    }
    rep(i, M) C[i].emplace_back(N+1);
    int ans = M;
    rep(i, M){
        rep(j, C[i].size()-1){
            if(C[i][j+1] - C[i][j] > M){
                ans = i;
                goto isAns;
            }
        }
    }

isAns:
    //output
    cout << ans << '\n';
}