#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using pii=pair<int,int>;
#define pb push_back
#define all(a) a.begin(),a.end()
#define sz(a) ((int)a.size())

const int mod=998244353,N=1<<21,G=3;

int add(int x, int y){x+=y; if(x>=mod) x-=mod; return x;}
int sub(int x, int y){x-=y; if(x<0) x+=mod; return x;}
int mul(int x, int y){return (ll)x*y%mod;}
int Pow(int x, ll y=mod-2){int res=1; for(; y; y>>=1,x=mul(x,x)) if(y&1) res=mul(res,x); return res;}

struct NTT{
    ll w[N];
    NTT(){
        ll dw=Pow(G,(mod-1)/N);
        w[0]=1;
        for(int i=1; i<N; ++i) w[i]=mul(w[i-1],dw);
    }
    void operator()(vector<int> &a, bool inv=false){
        int x=0,n=a.size();
        for(int j=1; j<n-1; ++j){
            for(int k=n>>1; (x^=k)<k; k>>=1);
            if(j<x) swap(a[j],a[x]);
        }
        for(int L=2; L<=n; L<<=1){
            int dx=N/L,dl=L>>1;
            for(int i=0; i<n; i+=L){
                for(int j=i,x=0; j<i+dl; ++j,x+=dx){
                    int tmp=mul(a[j+dl],w[x]);
                    a[j+dl]=sub(a[j],tmp);
                    a[j]=add(a[j],tmp);
                }
            }
        }
        if(inv){
            reverse(a.begin()+1,a.end());
            ll invn=Pow(n);
            for(int i=0; i<n; ++i) a[i]=mul(a[i],invn);
        }
    }
}ntt;

vector<int> mul(vector<int> a, vector<int> b, int bound=N){
    int m=a.size()+b.size()-1,n=1;
    while(n<m) n<<=1;
    a.resize(n),b.resize(n);
    ntt(a),ntt(b);
    vector<int> out(n);
    for(int i=0; i<n; ++i) out[i]=mul(a[i],b[i]);
    ntt(out,true),out.resize(min(m,bound));
    return out;
}

int n,val1[N],val2[N];
string s[4],t="TTPC";
bool a[N],b[N];

void ahcorz(){
    cin >> n; n--;
    for(int i=0; i<4; ++i){
        string de; cin >> de;
        s[i].clear();
        for(auto c: de) s[i]+='0'+(c==t[i]);
    }
    int m1=0,m2=0;
    {
        int pos1=0,pos2=0;
        for(int i=0; i<N; ++i){
            a[i]=(s[0][pos1]=='1'&&s[1][pos2]=='1');
            pos1++,pos2++;
            if(pos1>=sz(s[0])) pos1=0;
            if(pos2>=sz(s[1])) pos2=0;
            m1++;
            if(pos1==0&&pos2==0) break;
        }
    }
    {
        int pos1=0,pos2=0;
        for(int i=0; i<N; ++i){
            b[i]=(s[2][pos1]=='1'&&s[3][pos2]=='1');
            pos1++,pos2++;
            if(pos1>=sz(s[2])) pos1=0;
            if(pos2>=sz(s[3])) pos2=0;
            m2++;
            if(pos1==0&&pos2==0) break;
        }
    }
    vector<int> P(m1),Q(m2);
    //for(int i=0; i<m1; ++i) cout << a[i];
    //cout << '\n';
    //for(int i=0; i<m2; ++i) cout << b[i];
    //cout << '\n';
    for(int i=0; i<m1; ++i) P[i]=a[i];
    for(int i=0; i<m2; ++i) Q[i]=b[m2-1-i];
    vector<int> R=mul(P,Q);
    ll M=m1/__gcd(m1,m2)*m2;
    memset(val1,-1,sizeof val1),memset(val2,-1,sizeof val2);
    for(ll i=0; i<M; i+=m2) val1[i%m1]=i;
    for(ll i=0; i<M; i+=m1) val2[i%m2]=i;
    vector<pair<ll,ll>> vec;
    for(int i=0; i<m1; ++i) if(val1[i]>=0) vec.pb({val1[i],R[i+m2-1]});
    for(int i=1; i<m2; ++i) if(val2[i]>=0) vec.pb({val2[i],R[m2-1-i]});
    sort(all(vec));
    ll tot=0;
    for(auto &[x,y]: vec) tot+=y;
    if(tot==0){
        cout << "-1\n";
        return;
    }
    ll res=M*(n/tot);
    n%=tot;
    //cout << tot << "\n";
    for(auto &[x,y]: vec){
        //cout << x << ' ' << y << ' ' << n << "\n";
        if(n>=y){
            n-=y;
            continue;
        }
        for(int i=0; i<m1; ++i) if(val1[i]==x){
            for(int j=0; j<m2; ++j) if(i+j<m1&&a[i+j]&&b[j]){
                if(n==0){
                    res+=x+j;
                    break;
                }
                n--;
            }
            break;
        }
        for(int i=1; i<m2; ++i) if(val2[i]==x){
            for(int j=0; j<m1; ++j) if(i+j<m2&&a[j]&&b[i+j]){
                if(n==0){
                    res+=x+j;
                    break;
                }
                n--;
            }
            break;
        }
    }
    cout << res+1 << "\n";
}

signed main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    int t=1;// cin >> t;
    while(t--){
        ahcorz();
    }
}