#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 1e9+7;
const int N = 2e5+10;
ll dp[N][17];
int cnt[N][17];
string n;
int K;
int get(char c)
{
    if(c >= '0' && c <= '9')
        return c - '0';
    return c - 'A' + 10;
}

ll dfs(int pos, int k, bool limited, bool pre_zero)
{
    if(pos == n.size())
        return (k == K && !pre_zero) ? 1 : 0;
    if(!limited && !pre_zero && dp[pos][k] != -1)
        return dp[pos][k];
    ll ret = 0;
    int up = limited ? get(n[pos]) : 15;
    if(limited)
    {
        if(pre_zero)
        {
            //继续还是0
            ret = dfs(pos + 1, k, false, true);
            //选up
            ret = (ret + dfs(pos + 1, k + 1, true, false)) % MOD;
            //选择小于up但不是0的
            if(up > 1)
                ret = (ret + (up - 1) * dfs(pos + 1, k + 1, false, false)) % MOD;
        }
        else  
        {
            for(int i = 0; i <= up; ++i)
                ret = (ret + dfs(pos + 1, k + (cnt[pos][i] == 0), i == up, false)) % MOD;
        }
    }
    else  
    {
        if(pre_zero)
        {
            //选择0
            ret = dfs(pos + 1, k, false, pre_zero);
            //选择非0
            ret = (ret + dfs(pos + 1, k + 1, false, false) * up) % MOD;
        }
        else   
        {
            ret = dfs(pos + 1, k, false, false) * k + dfs(pos + 1, k + 1, false, false) * (up + 1 - k);
            ret %= MOD;
        }
    }
    if(!limited && !pre_zero)
        dp[pos][k] = ret;
    return ret;
}

int main()
{
    cin >> n >> K;
    memset(dp, -1, sizeof dp);
    for(int i = 0; i < n.size(); ++i)
    {
        cnt[i + 1][get(n[i])] = 1;
        for(int j = 0; j < 16; ++j)
            cnt[i + 1][j] += cnt[i][j];
    }
    
    cout << dfs(0, 0, true, true) << endl;
    return 0;
}
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define all(x) x.begin(),x.end()
#define mod 1000000007
#define ad(a,b) a=(a+b)%mod;
#define X 5010
ll po(ll x,ll y){
	ll res=1;
	for(;y;y>>=1){
		if(y&1)res=res*x%mod;
		x=x*x%mod;
	}
	return res;
}
ll fac[X],ivf[X];
void init(){
	fac[0]=1;
	for(ll i=1;i<X;i++)fac[i]=fac[i-1]*i%mod;
	for(ll i=0;i<X;i++)ivf[i]=po(fac[i],mod-2);
}
ll C(ll n,ll k){
	return fac[n]*ivf[n-k]%mod*ivf[k]%mod;
}

#define N 100010
ll calc(ll n,vector<ll> a,vector<ll> b,ll L){
	/*cerr<<"calc:"<<n<<" "<<L<<endl;
	cout<<"A:";rep(i,n)cout<<a[i]<<" ";cout<<endl;
	cout<<"B:";rep(i,n)cout<<b[i]<<" ";cout<<endl;*/
	rep(i,n){
		a[i]-=i,b[i]-=i;
	}
	L-=n;
	a.push_back(L);
	ll res=0;
	ll k=-1;//index kまで更新したことがある
	ll val=-1e17;//更新した値
	rep(i,n){
		if(val==b[i])continue;
		ll l=k,r=a.size(),mid;
		while(l<r-1){
			mid=(l+r)>>1;
			if(b[i]<=a[mid])r=mid;
			else l=mid;
		}
		if(r==a.size())return -1;
		if(a[r]!=b[i])return -1;
		res+=r-i;//i~r-1
		k=r-1,val=b[i];
	}
	//cout<<"res="<<res<<endl;
	return res;
}

ll n,L,a[N],b[N];
ll solve(){
	cin>>n>>L;
	L++;
	rep(i,n)cin>>a[i];
	rep(i,n)cin>>b[i];
	vector<ll> A,B;
	ll tbef=-1;
	ll hudobef=0;
	ll ans=0;
	rep(i,n+1){
		ll t=-1;
		if(i<n){
			if(a[i]<b[i])t=0;
			if(a[i]==b[i])t=1;
			if(a[i]>b[i])t=2;
		}
		else{
			a[i]=b[i]=L;
			t=1;
		}
		if(tbef!=t){
			if(tbef==0&&t==2)return -1;
			if(tbef==0){
				ll cres=calc(A.size(),A,B,a[i]);
				if(cres==-1)return -1;
				ans+=cres;
			}
			if(tbef==2){
				rep(i,A.size())A[i]*=-1,B[i]*=-1;
				reverse(all(A));
				reverse(all(B));
				ll cres=calc(A.size(),A,B,-hudobef);
				if(cres==-1)return -1;
				ans+=cres;
			}
			A.clear();
			B.clear();
			tbef=t;
		}
		if(t==1){
			hudobef=a[i];
		}
		A.push_back(a[i]);
		B.push_back(b[i]);
	}
	return ans;
}
int main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	cout<<solve()<<endl;
}
