#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for (int i=(x);i<=(y);i++)
#define drep(i,y,x) for (int i=(y);i>=(x);i--)
#define pii pair<int,int>
#define fir first
#define sec second
#define MP make_pair
template<typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template<typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
void file() {
    #ifdef zqj
    freopen("a.in","r",stdin);
    #endif
}
typedef long long ll;
#define sz 1111


void exgcd(ll a,ll b,ll &x,ll &y) {
    if (!b) return x=1,y=0,void();
    exgcd(b,a%b,y,x),y-=a/b*x;
}
ll exCRT(ll a1,ll p1,ll a2,ll p2) {
    ll a,b,g=gcd(p1,p2);
    if ((a1-a2)%g) return -1;
    exgcd(p1,p2,a,b);
    ll k=__int128((a2-a1)%p2+p2)*(a+p2)%p2;
    return p1/g*k+a1;
}
ll CRT(ll a1,ll a2,ll p1,ll p2){return exCRT(a1,p1,a2,p2);}
ll inv(ll x,ll mod) {
    if (mod==1) return 0;
    assert(gcd(x,mod)==1);
    ll a,b; exgcd(x,mod,a,b);
    a=(a%mod+mod)%mod;
    assert(a*x%mod==1);
    return a;
}

ll n;
char s[4][sz];
ll A,B,g,mod;

vector<ll>X[sz*sz],Y[sz*sz];

int check(ll R) {
    ll tt=0,aa=0;
    rep(t,0,g-1) tt+=1ll*X[t].size()*Y[t].size();
    tt*=R/mod; R%=mod;
    rep(t,0,g-1) for (auto x:X[t]) {
        ll _R=R-t;
        if (_R<=0) continue;
        ll y0=(-x+mod)%mod,y1=(_R-x+mod)%mod;
        if (y0<y1) {
            aa+=lower_bound(Y[t].begin(),Y[t].end(),y1)-lower_bound(Y[t].begin(),Y[t].end(),y0);
        }
        else {
            aa+=Y[t].size()+lower_bound(Y[t].begin(),Y[t].end(),y1)-lower_bound(Y[t].begin(),Y[t].end(),y0);
        }
    }
    return tt+aa>=n;
}

int main() {
    file();
    ios::sync_with_stdio(false), cin.tie(0);
    cin>>n;
    rep(i,0,3) cin>>s[i];
    A=lcm(strlen(s[0]),strlen(s[1])),B=lcm(strlen(s[2]),strlen(s[3]));
    g=gcd(A,B);
    // rep(t,0,g-1)
    //     rep(i,0,(int)strlen(s[0])/g-1) 
    //         rep(j,0,(int)strlen(s[1])/g-1) 
    //             if (s[0][i*g+t]=='T'&&s[1][j*g+t]=='T')
    //                 X[t].push_back(CRT())
    ll IAB = inv(A/g,B/g), IBA = inv(B/g,A/g);
    mod=lcm(A,B);
    rep(i,0,(int)strlen(s[0])-1) 
        rep(j,0,(int)strlen(s[1])-1) 
            if (s[0][i]=='T'&&s[1][j]=='T') {
                ll x=CRT(i,j,strlen(s[0]),strlen(s[1]));
                if (x==-1) continue;
                ll t=x%g; x/=g;
                X[t].push_back((__int128)x*B*IBA%mod);
            }
    rep(i,0,(int)strlen(s[2])-1) 
        rep(j,0,(int)strlen(s[3])-1) 
            if (s[2][i]=='P'&&s[3][j]=='C') {
                ll y=CRT(i,j,strlen(s[2]),strlen(s[3]));
                if (y==-1) continue;
                ll t=y%g; y/=g;
                Y[t].push_back((__int128)y*A*IAB%mod);
            }
    rep(t,0,g-1) sort(X[t].begin(),X[t].end()),sort(Y[t].begin(),Y[t].end());
    ll l=0,r=2e18,ans=-1;
    while (l<=r) {
        ll mid=(l+r)>>1;
        if (check(mid)) ans=mid,r=mid-1;
        else l=mid+1;
    }
    cout<<ans<<'\n';
    return 0;
}