#include <bits/stdc++.h>
using namespace std;
#define int long long
const int LIM = 2e18;
const int N = 1e6 + 10;
struct Seq {
    int len;
    vector<bool> s;
    inline void Init(char a, char b) {
        string s1, s2;
        cin >> s1 >> s2;
        len = (int)s1.size() * (int)s2.size() / __gcd(s1.size(), s2.size());
        s.resize(len);
        for (int i = 0; i < len; ++i) {
            s[i] = (s1[i % s1.size()] == a && s2[i % s2.size()] == b);
        }
    }
} s1, s2;
int f[N][60];
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    s1.Init('T', 'T');
    s2.Init('P', 'C');
    for (int i = 0; i < s2.len; ++i) {
        f[i][0] = s2.s[i];
    }
    int la = 0;
    for (int j = 1; j < 60; ++j) {
        for (int i = 0, ni = (1ll << j - 1) % s2.len * s1.len % s2.len; i < s2.len; ++i, ni = (ni + 1) % s2.len) {
            f[i][j] = f[i][j - 1] + f[ni][j - 1];
        }
        int sm = 0;
        for (int i = 0; i < s1.len; ++i) if (s1.s[i]) {
            sm += f[i % s2.len][j];
        }
        if (sm > n) break;
        la = j; 
    }
    if (la == 59) { cout << -1 << endl; return 0; }
    int ans = 0;
    for (int j = la; ~j; --j) {
        int sm = 0;
        for (int i = 0; i < s1.len; ++i) if (s1.s[i]) {
            sm += f[(ans + i) % s2.len][j];
        }
        if (sm < n) {
            ans += (1ll << j) * s1.len;
            n -= sm;
        }
    }
    // cout << la << ' ' << n << ' ' << ans << endl;
    for (int i = 0; i < s1.len; ++i) if (s1.s[i]) {
        n -= f[(ans + i) % s2.len][0];
        if (n == 0) {
            cout << ans + i + 1 << endl;
            break;
        }
    }
    return 0;
}