#include <bits/stdc++.h>

using namespace std;


#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define rep(i, n) for(int i = 0; i < n; i += 1)
#define len(a) (int(a.size()))


const ll inf = 1e18;
mt19937 rnd(234);


int32_t main() {
    if (1) {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }
    ll n, m;
    cin >> n >> m;
    string a, b;
    cin >> a >> b;
    string na, nb;
    for (auto x : a) {
        if (find(all(b), x) != b.end()) {
            na.push_back(x);
        }
    }
    for (auto x : b) {
        if (find(all(a), x) != a.end()) {
            nb.push_back(x);
        }
    }
    a = na;
    b = nb;
    if (a.empty() or b.empty()) {
        cout << 0 << "\n";
        return 0;
    }
    na = "";
    rep(i, n) na += a;
    n = 1;
    a = na;
    int s = len(a);
    int t = len(b);
    vector<ll> p(t);
    rep(i, t) p[i] = i;
    for (int i = 0; i < s; i += 1) {
        int first_same = -1;
        rep(j, t) if (a[i] == b[j]) { first_same = j; break; }
        assert(first_same != -1);
        vector<ll> np(t);
        for (int l = first_same; ; ) {
            int r = (l + 1) % t;
            while (a[i] != b[r]) {
                r = (r + 1) % t;
            }
            ll cur = p[l];
            if (l == t - 1) {
                cur -= t;
            }
            for (int j = (l + 1) % t; j != r; j = (j + 1) % t) {
                ll val = p[j];
                assert(val != cur);
                if (val < cur) {
                    np[j] = cur;
                    cur = val;
                } else {
                    np[j] = val;
                }
                if (j == t - 1) {
                    cur -= t;
                }
            }
            np[r] = cur;
            if (r == first_same) {
                break;
            }
            l = r;
        }
        p = np;
    }
    ll result = 0;
    rep(i, t) {
        if (p[i] >= 0) {
            continue;
        }
        ll f = (-p[i] + t - 1) / t;
        result += min(f, m);
    }
    cout << result << "\n";
    return 0;
}