优美的串

50分：
fi,S 表示长度为 i，按照 ABAB… 方式排列结尾情况为 S 的串
的个数。S 记录当前串的结尾有连续多少个 A 或连续个多少个
T。
那 S 的状态数一共为 2n 个。
对于 K ≤ 500 直接 dp，对于 K ≤ 109 矩乘 + 前缀和。

100分：
fi,SA,SB 记录长度为 i 的，所有以结尾为 A 子串的分割方式中最短的子串状态为 SA（若不存在以 A 结尾的分割方式，则 SA为空），所有以结尾为 B 子串的分割方式中最短的子串状态为SB （若不存在以 B 结尾的分割方式，则 SB 为空）的串的方案

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define R register
const int N=305,mod=1000000007;
int d,f[N][N];
char s[N],t[N];
struct sam
{
 int nn,lst,ch[N][4],len[N],lk[N];
 inline void init()
 {
  nn=lst=1;
  memset(ch,0,sizeof(ch));
 }
 inline void extend(int c)
 {
  int p=lst,np=lst=++nn;
  len[np]=len[p]+1;
  for(;p&&!ch[p][c];p=lk[p])
   ch[p][c]=np;
  if(!p)
   lk[np]=1;
  else
  {
   int q=ch[p][c],nq;
   if(len[q]==len[p]+1)
    lk[np]=q;
   else
   {
    nq=++nn;
    len[nq]=len[p]+1;
    lk[nq]=lk[q];
    lk[q]=lk[np]=nq;
    memcpy(ch[nq],ch[q],sizeof(ch[q]));
    for(;p&&ch[p][c]==q;p=lk[p])
     ch[p][c]=nq;
   }
  }
 }
}A,B;
struct mat
{
 int a[N][N];
 mat(int x=0)
 {
  memset(a,0,sizeof(a));
  for(int i=1;i<=d;++i)
   a[i][i]=x;
 }
};
inline mat operator*(const mat&a,const mat&b)
{
 mat c(0);
 for(R int i=1;i<=d;++i)
 {
  for(R int j=1;j<=d;++j)
  {
   ll r=0;
   for(R int k=1;k<=d;)
   {
    r+=1ll*a.a[i][k]*b.a[k][j];++k;
    r+=1ll*a.a[i][k]*b.a[k][j];++k;
    r+=1ll*a.a[i][k]*b.a[k][j];++k;
    r+=1ll*a.a[i][k]*b.a[k][j];++k;
    r+=1ll*a.a[i][k]*b.a[k][j];++k;
    r+=1ll*a.a[i][k]*b.a[k][j];++k;
    r+=1ll*a.a[i][k]*b.a[k][j];++k;
    r+=1ll*a.a[i][k]*b.a[k][j];++k;
    r%=mod;
   }
   c.a[i][j]=r;
  }
 }
 return c;
}
inline mat pw(mat a,int b)
{
 mat r(1);
 for(;b;b>>=1,a=a*a)
  if(b&1)
   r=r*a;
 return r;
}
inline int id(char c)
{
 return c=='A'?0:(c=='C'?1:(c=='G'?2:3));
}
inline int gtid(int &x)
{
 return !x?x=++d:x;
}
int main()
{
 int T;scanf("%d",&T);
 while(T--)
 {
  int n,m,k;scanf("%d%d%d",&n,&m,&k);
  scanf("%s%s",s,t);A.init();B.init();
  for(R int i=0;i<n;++i)A.extend(id(s[i]));
  for(R int i=0;i<m;++i)B.extend(id(t[i]));
  memset(f,0,sizeof(f));d=0;
  for(R int i=1;i<=A.nn;++i)gtid(f[i][1]);
  for(R int i=1;i<=A.nn;++i)for(R int j=0;j<4;++j)if(B.ch[1][j])gtid(f[i][B.ch[1][j]]);
  for(R int i=1;i<=B.nn;++i)gtid(f[1][i]);
  for(R int i=1;i<=B.nn;++i)for(R int j=0;j<4;++j)if(A.ch[1][j])gtid(f[A.ch[1][j]][i]);
  d++;mat st,tr;tr.a[d][d]=1;
  for(R int i=1;i<=A.nn;++i)for(R int j=1;j<=B.nn;++j)if(f[i][j])
  {
   if(j>1)tr.a[f[i][j]][d]=1;
   for(R int k=0;k<4;++k)
   {
    int ii=j>1&&A.ch[1][k]?A.ch[1][k]:(i==1||!A.ch[i][k]?1:A.ch[i][k]);
    int jj=i>1&&B.ch[1][k]?B.ch[1][k]:(j==1||!B.ch[j][k]?1:B.ch[j][k]);
    tr.a[f[i][j]][f[ii][jj]]++;
   }
  }
  for(R int i=0;i<4;++i)if(A.ch[1][i])st.a[1][f[A.ch[1][i]][1]]++;
  st=st*pw(tr,k);printf("%d\n",st.a[1][d]);
 }
 return 0;
}