#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

typedef long long ll;
typedef pair<int, int> pii;

template<typename T>
std::ostream& operator << (std::ostream& os, const vector<T>& a) {
    for (const T& x : a) {
        os << x << ' ';
    }
    return os;
}

template<class T>
void red(T& r, T a) {
    r = ((r % a) + a) % a;
}
template<class T>
T mod_inv(T r, T a) {
    T g = a; T z = 0; T y = 1;
    while (r != 0) {
        T q = g / r;
        g %= r;
        swap(g, r);
        z -= q * y;
        swap(z, y);
    }
    return z < 0 ? z + a : z;
}
template<class T>
pair<T, T> crt(T ra, T a, T rb, T b) {
    red(ra, a);
    red(rb, b);
    T d = __gcd(a, b);
    if (ra % d != rb % d) {
        return {0, 0};
    }
    a /= d;
    b /= d;
    T mod = a * b;
    T r = 0;
    r = (r + ((ra / d) * b % mod) * mod_inv(b, a) % mod) % mod;
    r = (r + ((rb / d) * a % mod) * mod_inv(a, b) % mod) % mod;
    mod *= d;
    T res = (r * d % mod + ra % d) % mod;
    return {res, mod};
}

template <int mod>
struct Modular {
    int val;
    Modular() : val(0) {}
    Modular(int _val) : val(_val) {}
    friend Modular operator+(const Modular& a, const Modular& b) {
        return a.val + b.val >= mod ? a.val + b.val - mod : a.val + b.val;
    }
    friend Modular operator-(const Modular& a, const Modular& b) {
        return a.val - b.val < 0 ? a.val - b.val + mod : a.val - b.val;
    }
    friend Modular operator*(const Modular& a, const Modular& b) {
        return 1ll * a.val * b.val % mod;
    }
    Modular& operator*=(const Modular& ot) {
        return *this = *this * ot;
    }
    friend Modular binpow(Modular a, ll n) {
        Modular res = 1;
        for (; n >= 1; n >>= 1, a *= a) {
            if (n & 1) {
                res *= a;
            }
        }
        return res;
    }
    friend Modular inv(const Modular& a) {
        return binpow(a, mod - 2);
    }
    friend Modular operator/(const Modular& a, const Modular& b) {
        return a * inv(b);
    }
};

template <int mod>
ostream& operator<<(ostream& ostr, Modular<mod> x) {
    return ostr << x.val;
}


template<int mod = 469762049, int root = 3>
class NTT {
    using Mint = Modular<mod>;
public:
    static vector<int> mult(const vector<int>& a, const vector<int>& b) {
        vector<Mint> A(a.size());
        vector<Mint> B(b.size());
        for (int i = 0; i < a.size(); ++i) {
            A[i] = a[i];
        }
        for (int i = 0; i < b.size(); ++i) {
            B[i] = b[i];
        }
        vector<Mint> C = mult(A, B);
        vector<int> res(C.size());
        for (int i = 0; i < C.size(); ++i) {
            res[i] = C[i].val;
        }
        return res;
    }
    static vector<Mint> mult(const vector<Mint>& a, const vector<Mint>& b) {
        int n = int(a.size()), m = int(b.size());
        if (!n || !m) return {};
        int lg = 0;
        while ((1 << lg) < n + m - 1) {
            ++lg;
        }
        int z = 1 << lg;
        auto a2 = a, b2 = b;
        a2.resize(z);
        b2.resize(z);
        nft(false, a2);
        nft(false, b2);
        for (int i = 0; i < z; ++i) {
            a2[i] *= b2[i];
        }
        nft(true, a2);
        a2.resize(n + m - 1);
        Mint iz = inv(Mint(z));
        for (int i = 0; i < n + m - 1; ++i) {
            a2[i] *= iz;
        }
        return a2;
    }
private:
    static void nft(bool type, vector<Mint> &a) {
        int n = int(a.size()), s = 0;
        while ((1 << s) < n) ++s;
        assert(1 << s == n);
        static vector<Mint> ep, iep;
        while (int(ep.size()) <= s) {
            ep.push_back(binpow(Mint(root), (mod - 1) / (1 << ep.size())));
            iep.push_back(inv(ep.back()));
        }
        vector<Mint> b(n);
        for (int i = 1; i <= s; ++i) {
            int w = 1 << (s - i);
            Mint base = type ? iep[i] : ep[i], now = 1;
            for (int y = 0; y < n / 2; y += w) {
                for (int x = 0; x < w; x++) {
                    auto l = a[(y << 1) | x];
                    auto r = now * a[(y << 1) | x | w];
                    b[y | x] = l + r;
                    b[y | x | (n >> 1)] = l - r;
                }
                now *= base;
            }
            swap(a, b);
        }
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif

    int N;
    cin >> N;
    --N;

    vector<vector<int>> vecs;
    string pattern = "TTPC";
    for (int it = 0; it < 4; it += 2) {
        string s, t;
        cin >> s >> t;
        int m1 = s.size(), m2 = t.size();
        int m = m1 * m2 / gcd(m1, m2);
        vector<int> a(m);
        for (int i = 0; i < m1; ++i) {
            for (int j = 0; j < m2; ++j) {
                if (s[i] == pattern[it] && t[j] == pattern[it + 1]) {
                    //cout << i << ' ' << m1 << ' ' << j << ' ' << m2 << '\n';
                    auto [rem, mod] = crt(i, m1, j, m2);
                    if (mod != 0) {
                        a[rem] = 1;
                    }
                }
            }
        }
        vecs.push_back(a);
    }

    vector<int> a = vecs[0], b = vecs[1];
    if (a.size() > b.size()) {
        swap(a, b);
    }

    //cout << a << '\n';
    //cout << b << '\n';

    ll M1 = b.size();
    ll M2 = a.size();

    ll pairs = 0;
    ll G = gcd(M1, M2);
    vector<int> cnta(G);
    for (int i = 0; i < a.size(); ++i) {
        cnta[i % G] += a[i];
    }
    vector<int> cntb(G);
    for (int i = 0; i < b.size(); ++i) {
        cntb[i % G] += b[i];
    }
    for (int i = 0; i < G; ++i) {
        pairs += cnta[i] * 1LL * cntb[i];
    }
    //cout << "pairs = " << pairs << '\n';

    if (pairs == 0) {
        cout << "-1\n";
        return 0;
    }

    ll ans = (M1 * M2 / G) * (N / pairs);
    N %= pairs;

    vector<int> A = a;
    while (A.size() < b.size()) {
        for (int x : a) {
            A.push_back(x);
        }
    }
    vector<int> B = b;
    reverse(all(B));

    vector<int> C = NTT<>::mult(A, B);

    for (int x = 0; x < M2 / G; ++x) {
        int rem = (x * M1) % M2;
        int cnt = C[rem + M1 - 1];
        if (N >= cnt) {
            ans += M1;
            N -= cnt;
        } else {
            for (int y = 0; y < M1; ++y) {
                if (b[y] == 1 && a[(x * M1 + y) % M2] == 1) {
                    if (N == 0) {
                        cout << ans + 1 << '\n';
                        return 0;
                    }
                    --N;
                }
                ++ans;
            }
        }
    }

    return 0;
}