#include <bits/stdc++.h>
using namespace std;
#define SELECTER(_1, _2, _3, SELECT, ...) SELECT
#define REP1(i, n) for(int i=0; (i)<(n); (i)++)
#define REP2(i, a, b) for(int i=(a); (i)<(b); (i)++)
#define REP(...) SELECTER(__VA_ARGS__, REP2, REP1,) (__VA_ARGS__)
#define MOD 1'000'000'007

template <class T> ostream& operator<<(ostream& os, const vector<T>& v){ os << "{"; for(size_t i=0; i<v.size(); i++) os << v[i] << (i+1==v.size() ? "" : ", "); os << "}"; return os; }
template <class T, class U> ostream& operator<<(ostream& os, const pair<T, U>& p){ return os << "{" << p.first << ", " << p.second << "}"; }

int main(){
    int N, M;
    cin >> N >> M;
    vector<int> A(N+2), B(M+2);
    REP(i, N) cin >> A[i+1];
    REP(i, M) cin >> B[i+1];

    vector<vector<int>> dp(N+2, vector<int>(M+2, 1<<30));
    dp[0][0] = 0;
    for(int i=0; i<=N; i++){
        for(int j=0; j<=M; j++){
            dp[i][j+1] = min(dp[i][j+1], dp[i][j] + 1);
            dp[i+1][j] = min(dp[i+1][j], dp[i][j] + 1);
            int tmp = (A[i+1] == B[j+1]) ? 0 : 1;
            dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j] + tmp);
        }
    }
    cout << dp[N][M] << endl;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define deb(k) cerr << #k << ": " << k << "\n";
#define size(a) (int)a.size()
#define fastcin cin.tie(0)->sync_with_stdio(0);
#define st first
#define nd second
#define pb push_back
#define mk make_pair
#define int long long
typedef long double ldbl;
typedef double dbl;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef map<int, int> mii;
typedef vector<int> vint;
#define MAXN 300100
#define MAXLG 20
const int inf = 0x3f3f3f3f;
const ll mod = 1000000007;
const ll linf = 0x3f3f3f3f3f3f3f3f;
const int N = 300100;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int f(char c){
	if('A' <= c && c <= 'F') return 10 + c - 'A';
	return c - '0';
}

int dp[200100][18];
bool w[16];

void solve(){
	string s;
	int k;
	cin>>s>>k;
	int n = size(s);
	int cnt = 0;

	for(int i=0;i<n;i++){
		for(int j=0;j<=16;j++){
			dp[i+1][j] += j * dp[i][j];
			dp[i+1][j] %= mod;

			dp[i+1][j+1] += (16 - j)*dp[i][j];
			dp[i+1][j+1] %= mod;
		}
		if(i){
			dp[i+1][1] += 15;
			dp[i+1][1] %= mod;
		}

		for(int j=0;j<f(s[i]);j++){
			if( i == 0 && j == 0 ) continue;

			if(w[j]){
				dp[i+1][cnt] += 1;
				dp[i+1][cnt] %= mod;
			}
			else{
				dp[i+1][cnt+1] += 1;
				dp[i+1][cnt+1] %= mod;
			}
		}

		if(!w[f(s[i])]){
			w[f(s[i])] = 1;
			cnt++;
		}
	}

	if(cnt == k){
		dp[n][k] += 1;
		dp[n][k] %= mod;
	}
	cout<<dp[n][k]<<"\n";





	// Have you read the problem again?
	// Maybe you understood the wrong problem
}

int32_t main(){
	fastcin;
	int t_ = 1;
	//cin>>t_;
	while(t_--)
		solve();
	return 0;
}
