#include<bits/stdc++.h>
#define PI 3.141592653589793238462
#define eps 1e-20
using namespace std;
typedef long long ll;
typedef long double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<db,db> pdd;
ll a[200005],d[200005][20],vis[20],mod=1e9+7;
int main(){
    string s;ll k;cin>>s>>k;
    ll n=s.length(),t=0;s=" "+s;
    for(ll i=1;i<=n;i++){
        if(s[i]>='A') a[i]=(s[i]-'A')+10;
        else a[i]=(s[i]-'0');
    }
    d[1][1]=a[1]-1;
    for(ll i=1;i<n;i++){
        if(!vis[a[i]]){
            t++;vis[a[i]]=1;
        }
        for(ll j=1;j<=k;j++){
            d[i+1][j]+=d[i][j]*j;d[i+1][j]%=mod;
            if(j+1<=16) d[i+1][j+1]+=d[i][j]*(16-j),d[i+1][j+1]%=mod;
        }
        for(ll j=0;j<a[i+1];j++){
            if(vis[j]) d[i+1][t]++;
            else d[i+1][t+1]++;
        }
        d[i+1][1]+=15;d[i+1][1]%=mod;
    }
    if(vis[a[n]]) d[n][t]++;
    else d[n][t+1]++;
    cout<<d[n][k]%mod<<endl;
}

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define all(a) a.begin(),a.end()
#define fi first
#define se second
#define deb(x) cout << #x << "=" << x << endl
#define clr(x) memset(x, 0, sizeof(x))
#define rep(i,k,n) for(int i=k;k<n?i<n:i>n;k<n?i+=1:i-=1)
int M=1e9+7,N=205001;
 
int mm(int x,int y){x%=M,y%=M;return (x*y)%M;}//Modular Multiply
int po(int x,int y){ if(!y)return 1;int a=po(x,y/2)%M;if(y%2)return mm(a,mm(a,x));return mm(a,a);}//(x**y)%M
 
 
 
int solve(vector<int>& h) {
    int n=h.size(),mx=0;
    if(!n) return 0;
    int nsl[n],nsr[n];
    stack<int> s;
    for(int i=0;i<n;i++){
        while(!s.empty() and h[s.top()]>=h[i]) s.pop();
        nsl[i]=((s.empty())?-1:s.top());
        s.push(i);
    }
    while(!s.empty()) s.pop();
    for(int i=n-1;i>=0;i--){
        while(!s.empty() and h[s.top()]>=h[i]) s.pop();
        nsr[i]=((s.empty())?n:s.top());
        s.push(i);
    }
    for(int i=0;i<n;i++)
        mx=max(mx,h[i]*(nsr[i]-nsl[i]-1)); 
    return mx;
}
 
 
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n;
	cin>>n;
	vector<int> h(n);
	rep(i,0,n) cin>>h[i];
	cout<<solve(h); 
}