首先观察数据范围和题意，我们猜测这是一道DP题。
我们首先维护\(f_{i,j,k}\)表示，对于\(B\)中的前\(i\)个字符，在\(A\)中的前\(k\)个字符中，可以用\(j\)个子串来完成匹配。
那么，对于一个当前的字符\(i\)，它如果需要匹配，我们有两种匹配方法：一是加到已有的串，二是新开一个串。
加到已有的串是很好转移的，直接\(f_{i+1,j,k+1}+=(A_{k+1}==B_{i+1})*f_{i,j,k}\)；
而如果是新开一个串，朴素的考虑肯定是从\(k\)往后扫，然后把状态转移到所有之后的可行的位置：\(f_{i+1,j+1,S}+=f{i,j,k}\)。
但将一个状态转移到多个状态的加速转移是很难实现的，所以我们考虑使用填表法。
很容易可以发现，对于一个状态\(f_{i,j,k}\)，它可以从上述的两种状态转移到。
故而我们可以得到一个朴素的转移方程：
\(f_{i,j,k}=(A_{k}==B_{i})*f_{i-1,j,k-1}+\sum_{S=i}^{k}f_{i-1,j-1,S}\)
观察可以发现，这个转移方程的复杂度瓶颈在于后面那个求和式——这使得整个转移的复杂度是\(O(n^{2}*m*k)\)的。
我们考虑优化转移。区间求和的转移优化已经可以说是套路了，我们只需要简单地维护一个前缀和即可。
用\(sm_{i,j,k}\)表示，要用\(1~k\)中的串\(j\)个串填充\(1~i\)的位置的方案数。
同时,\(40000000\)的空间复杂度对于\(128MB\)的内存限制来说是非常危险的。所以我们考虑滚动数组。
这样就做完了。
#include<iostream>
#include<cstdio>
/*
*/
const long long MOD=1000000007;
int n,m,K;
long long f[2][205][1005],sm[2][205][1005];
char A[1005],B[205];
void init(){
scanf("%d%d%d",&n,&m,&K);
std::cin>>(A+1)>>(B+1);
int nw=1;sm[0][0][0]=1;
for(int i=1;i<=n;++i){
sm[nw][0][0]=1;
for(int j=1;j<=m;++j){
for(int k=1;k<=K;++k){
f[nw][j][k]=(A[i]==B[j])?((f[nw^1][j-1][k]+sm[nw^1][j-1][k-1])%MOD):0;
sm[nw][j][k]=(sm[nw^1][j][k]+f[nw][j][k])%MOD;
}
}
nw^=1;
}
printf("%lld\n",sm[nw^1][m][K]);
}
int main(){
init();
return 0;
}