#include <bits/stdc++.h>
typedef long long ll;
using namespace std;


const int N = 2e5 + 5, mod = 1e9 + 7;
char s[N];
int a[N], k;
int add (int a, int b) {
	return ((a += b) >= mod) ? (a - mod) : a;
}
int dp[N][20], K;
int f (int l, int k) {
	if (~dp[l][k]) return dp[l][k];
	if (l == 0) return k == K;
	dp[l][k] = (ll)k * f(l - 1, k) % mod;
	if (k)
		dp[l][k] = add(dp[l][k], (ll)f(l - 1, k + 1) * (16 - k) % mod);
	return dp[l][k];
}
int main() {
	memset (dp, -1, sizeof (dp));
	cin >> (s + 1) >> K;
	int len = strlen(s + 1);
	for (int i = 1; i <= len; ++i) {
		if (isdigit(s[i])) a[i] = s[i] - '0';
		else a[i] = s[i] - 'A' + 10;
	}
	
	int ans = 0;
	for (int i = len; i >= 2; --i) {
		for (int j = 1; j < 16; ++j) ans += f (len - i, 1), ans %= mod;
		ans %= mod;
	}
	
//	cerr << ans << '\n';
	int st = 0;
	for (int i = 1; i <= len; ++i) {
		for (int j = ((i == 1) ? 1 : 0); j < a[i]; ++j) {
			int newst = st | (1 << j), cnt = __builtin_popcount(newst);
		//	cerr << len - i << " " << cnt << ":" << f(len - i, cnt) << '\n';
			ans = add(ans, f(len - i, cnt));
		}
		st |= (1 << a[i]);
	}
	if (__builtin_popcount(st) == K) ans = add(ans, 1);
	cout << ans << '\n';
	return 0;
}


#include<bits/stdc++.h>
#define maxn 2000010
using namespace std;
typedef long long LL;
int read()
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
	return s*w;
}
int n,m,a[maxn],s[maxn<<2],c[maxn<<2];
void ins(int k,int l,int r,int p,int vl)
{
	if(l==r) return c[k]+=vl,s[k]=(c[k]?1:0),void(0);int mid=l+r>>1;
	p>mid?ins(k<<1|1,mid+1,r,p,vl):ins(k<<1,l,mid,p,vl),s[k]=s[k<<1]+s[k<<1|1];
}
int ask(int k,int l,int r)
{
	if(l==r) return l;int mid=l+r>>1;
	if(s[k<<1]==mid-l+1) return ask(k<<1|1,mid+1,r);
	else return ask(k<<1,l,mid);
}
signed main()
{
	int ans=0x7fffffff;
	n=read(),m=read();
	for(int i=1;i<=n;i++) a[i]=read()+1;
	for(int i=1;i<=m;i++) ins(1,1,n+1,a[i],1);
	ans=min(ans,ask(1,1,n+1));
	for(int i=m+1;i<=n;i++) ins(1,1,n+1,a[i-m],-1),ins(1,1,n+1,a[i],1),ans=min(ans,ask(1,1,n+1));
	cout<<ans-1<<'\n';
	return 0;
}