Gym 101848H

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define ll long long
#define db double
#define fr friend
#define op operator

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int N=1<<20|7;

int gcd(int a,int b){
    return b?gcd(b,a%b):a;
}

struct comp{
    double r,i;
    comp():r(0),i(0){}
    comp(const double &_r,const double &_i):r(_r),i(_i){}
}F[N],G[N],Wn[N];

inline comp operator + (const comp &a,const comp &b){
    return comp(a.r+b.r,a.i+b.i);
}

inline comp operator - (const comp &a,const comp &b){
    return comp(a.r-b.r,a.i-b.i);
}

inline comp operator * (const comp &a,const comp &b){
    return comp(a.r*b.r-a.i*b.i,a.r*b.i+a.i*b.r);
}

inline comp operator / (const comp &a,const double &b){
    return comp(a.r/b,a.i/b);
}

inline comp conj(const comp &a){
    return comp(a.r,-a.i);
}

int len;
int r[N];
const db pi=acos(-1.0);
const comp Tmp=comp(0,-0.25);

inline void DFT(comp *t){
    for(int i=0;i<len;++i)if(i<r[i])swap(t[i],t[r[i]]);
    for(int i=1;i<len;i<<=1){
        comp wn(Wn[i].r,Wn[i].i);
        for(int j=0;j<len;j+=(i<<1)){
            comp w(1,0);
            for(int k=0;k<i;++k,w=w*wn){
                comp u=t[j+k];
                comp v=w*t[j+k+i];
                t[j+k]=u+v;
                t[j+k+i]=u-v;
            }
        }
    }
}

inline void IDFT(comp *t){
    for(int i=0;i<len;++i)if(i<r[i])swap(t[i],t[r[i]]);
    for(int i=1;i<len;i<<=1){
        comp wn(Wn[i].r,-Wn[i].i);
        for(int j=0;j<len;j+=(i<<1)){
            comp w(1,0);
            for(int k=0;k<i;++k,w=w*wn){
                comp u=t[j+k];
                comp v=w*t[j+k+i];
                t[j+k]=u+v;
                t[j+k+i]=u-v;
            }
        }
    }
    for(int i=0;i<len;++i)t[i].r/=len;
}

char s[N],t[N];

int Ans[N];

int main(){
    int n,m,l=0;ll k;read(n),read(m),read(k);
    if(n<m)scanf("%s%s",t,s),swap(n,m);
    else scanf("%s%s",s,t);

    memcpy(s+n,s,n);
    n<<=1;reverse(s,s+n);

    for(len=1;len<=max(m,n);len<<=1)++l;
    for(int i=0;i<len;++i)r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    for(int i=1;i<len;i<<=1)Wn[i]=comp(cos(pi/i),sin(pi/i));

    for(int i=0;i<len;++i)F[i]=comp(s[i]=='A',t[i]=='A');
    DFT(F);
    for(int i=0,j;i<len;++i)j=(len-i)&(len-1),G[j]=G[j]+(F[j]*F[j]-conj(F[i]*F[i]))*Tmp;

    for(int i=0;i<len;++i)F[i]=comp(s[i]=='T',t[i]=='T');
    DFT(F);
    for(int i=0,j;i<len;++i)j=(len-i)&(len-1),G[j]=G[j]+(F[j]*F[j]-conj(F[i]*F[i]))*Tmp;

    for(int i=0;i<len;++i)F[i]=comp(s[i]=='G',t[i]=='G');
    DFT(F);
    for(int i=0,j;i<len;++i)j=(len-i)&(len-1),G[j]=G[j]+(F[j]*F[j]-conj(F[i]*F[i]))*Tmp;

    for(int i=0;i<len;++i)F[i]=comp(s[i]=='C',t[i]=='C');
    DFT(F);
    for(int i=0,j;i<len;++i)j=(len-i)&(len-1),G[j]=G[j]+(F[j]*F[j]-conj(F[i]*F[i]))*Tmp;

    IDFT(G);

    reverse(s,s+n);n>>=1;
    for(int i=0;i<n;++i)Ans[i]=int(G[2*n-1-i].r+0.5);
    // for(int i=0;i<n;++i)printf("%d ",Ans[i]);

    ll ans=0;
    ll period=(ll)n/gcd(n,m)*m;
    ll pos;
    for(pos=0;pos<period;pos+=m){
        ans+=Ans[pos%n];
    }
    ans*=(k/period);
    ll remain=k%period;
    for(pos=0;pos+n<remain;pos+=m){
        ans+=Ans[pos%n];
    }
    for(;pos<remain;++pos){
        ans+=(s[pos%n]==t[pos%m]);
    }
    printf("%lld\n",ans);
    return 0;
}