#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;
    }
    auto check_perm = [&](vector<ll> x) {
        for (auto& v : x) {
            v = ((v % t) + t) % t;
        }
        sort(all(x));
        rep(i, t) if (x[i] != i) return false;
        return true;
        };
    auto merge = [&](const vector<ll>& p, const vector<ll>& q) {
        vector<ll> invq(t, t);
        rep(i, t) {
            ll val = q[i];
            ll r = ((val % t) + t) % t;
            ll d = (val - r) / t;
            assert(d <= 0);
            invq[r] = (-d) * t + i;
        }
        assert(check_perm(invq));
        vector<ll> biba, boba;
        vector<ll> base;
        rep(i, t) {
            biba.push_back(p[i]);
            biba.push_back(p[i] + t);
            base.push_back(p[i] + t);
            biba.push_back(p[i] + 2 * t);

            boba.push_back(invq[i]);
            boba.push_back(invq[i] + t);
            boba.push_back(invq[i] + 2 * t);
        }
        sort(all(biba));
        sort(all(boba));
        sort(all(base));
        biba.resize(unique(all(biba)) - biba.begin());
        boba.resize(unique(all(boba)) - boba.begin());
        base.resize(unique(all(base)) - base.begin());
        assert(len(biba) == 3 * t);
        assert(len(boba) == 3 * t);
        assert(len(base) == t);
        vector<ll> a(3 * t), b(3 * t);
        rep(i, t) {
            a[i] = lower_bound(all(biba), p[i]) - biba.begin();
            a[i + t] = lower_bound(all(biba), p[i] + t) - biba.begin();
            a[i + 2 * t] = lower_bound(all(biba), p[i] + 2 * t) - biba.begin();

            b[lower_bound(all(boba), invq[i]) - boba.begin()] = i;
            b[lower_bound(all(boba), invq[i] + t) - boba.begin()] = i + t;
            b[lower_bound(all(boba), invq[i] + 2 * t) - boba.begin()] = i + 2 * t;
        }
        vector<pair<int, int>> swaps;
        while (true) {
            bool flag = false;
            for (int i = 0; i + 1 < 3 * t; i += 1) {
                if (b[i] > b[i + 1]) {
                    swaps.push_back(make_pair(i, i + 1));
                    swap(b[i], b[i + 1]);
                    flag = true;
                }
            }
            if (!flag) {
                break;
            }
        }
        reverse(all(swaps));
        for (auto [i, j] : swaps) {
            if (a[i] < a[j]) {
                swap(a[i], a[j]);
            }
        }
        vector<ll> result(t, t);
        rep(i, 3 * t) {
            int j = a[i];
            ll x = biba[j];
            if (binary_search(all(base), x)) {
                ll y = boba[i];
                ll ry = (y % t + t) % t;
                result[ry] = (x - (y - ry));
            }
        }
        assert(check_perm(result));
        return result;
        };
    function<vector<ll>(const vector<ll>&, int)> bin_pow;
    bin_pow = [&](const vector<ll>& p, int n) {
        if (n == 0) {
            vector<ll> res(t); rep(i, t) res[i] = i; return res;
        }
        auto a = bin_pow(p, n / 2);
        a = merge(a, a);
        if (n & 1) {
            a = merge(a, p);
        }
        return a;
        };
    auto q = bin_pow(p, n);
    ll result = 0;
    rep(i, t) {
        if (q[i] >= 0) {
            continue;
        }
        ll f = (-q[i] + t - 1) / t;
        result += min(f, m);
    }
    cout << result << "\n";
    return 0;
}