看到各位DP数组都只开两三维的我很害怕啊，我来讲一讲如何很暴力的做这道题。

状态

首先我们考虑设计状态。我们发现，为了保证无后效性的一位一位往后推，我们需要记录当前推到$a$串的哪一个位置了；接着还有记录匹配了$b$串的那几个字符。因为是按照原串顺序，所以相当于是即匹配$b$的前几个字符。有这些还不够，我们还要记录划分了几个子串。最后，为了便于转移，我们还要标记一维0/1状态，表示$a$串中的第$i$个字符是否选入。

这样，我们就设计好了状态。我们记$f_{i,j,p,v}$表示到$a$串的第$i$个位置为止使用$p$个子串匹配$b$串前$j$位字符且第$i$个位置选或不选（$v$）的方案数。

转移

设计好状态，不会转移怎么行。我们分情况考虑。

1. 当$a_i=b_j$时：

   1. $f_{i,j,p,0}$：由于这位不选，所以就是前面一位选和不选方案数之和，即$f_{i,j,p,0}=f_{i-1,j,p,0}+f_{i-1,j,p,1}$。

   2. 容易得到$f_{i,j,p,1}=f_{i-1,j-1,p,1}+f_{i-1,j-1,p-1,0}+f_{i-1,j-1,p-1,1}$.

2. 当$a_i\ne b_j$时：

   1. 不选情况同上，即$f_{i,j,p,0}=f_{i-1,j,p,0}+f_{i-1,j,p,1}$.

   2. 由于选不了，自然就是$0$，即$f_{i,j,p,1}=0$.

优化空间

如果你读完状态设计之后又稍微思考就会发现，空间可能较大。空间不够怎么办？在luogu还好说，如果真的在NOIP，应该是不敢开$1000\times200\times200\times2=8\times10^7$的数组吧。所以我们观察转移方程，发现每次转移只用到了前一位！于是我们把第一维很愉快地滚掉了。这样，空间复杂度就保证是$O(mk)$了。那么时间呢？时间是$O(n\cdot mk)$，但是时间不像空间，这个复杂度是可以接受的。于是，完整算法就结束了。

Cpp代码：

#include<cstdio>
#include<cstring>
const int MAXN=1010;
const int MAXM=210;
const int MOD=(int)(1e9)+7;
int f[2][MAXM][MAXM][2];
char a[MAXN],b[MAXM];
int n,m,k;bool val=1;

void dp(){
    f[0][0][0][0]=f[1][0][0][0]=1;
    for(int i=1;i<=n;i++,val^=1)
        for(int j=1;j<=m;j++)
            for(int p=1;p<=k;p++){
                if(a[i]==b[j]){
                    f[val][j][p][0]=(f[val^1][j][p][0]+f[val^1][j][p][1])%MOD;
                    f[val][j][p][1]=(f[val^1][j-1][p][1]+\
                                    (f[val^1][j-1][p-1][0]+f[val^1][j-1][p-1][1])%MOD)%MOD;
                }
                else{
                    f[val][j][p][0]=(f[val^1][j][p][0]+f[val^1][j][p][1])%MOD;
                    f[val][j][p][1]=0;
                }
            }
}

int main(){
    scanf("%d%d%d",&n,&m,&k);
    scanf("%s%s",a+1,b+1);
    dp();
    printf("%d\n",(f[n&1][m][k][0]+f[n&1][m][k][1])%MOD);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1005, M=205;
const LL P=1e9+7;
char s1[N], s2[M];
LL f[M][M], g[M][M]; 
//f[j][k]代表在当前 s1[i]匹配 s2[j]（s1[i]=s2[j]时才不为 0），分成 k段的方法数  
//g[j][k]代表在当前 s1[i]匹配 s2前 j个（s1[i]!=s2[j]时也有值），分成 k段的方法数总和，类似于 f[j][k]的前缀和 
//其实 g[m][K]是代表当前 s1[i]匹配所有 s2[j]的方法数，包括能匹配和不能匹配 
int main()
{
    int n, m, K; scanf("%d%d%d", &n, &m, &K);
    scanf("%s%s", s1+1, s2+1);
    memset(f, 0, sizeof(f)); memset(g, 0, sizeof(g)); 
    for(int k=1; k<=K; k++) f[0][k]=1; //边界，匹配到 s2[0]等于 1 
    for(int i=1; i<=n; i++)
        for(int j=min(i, m); j>=1; j--) //从大到小是因为状态转移需要上一个 i的，正着来会用到这次的，而j不大于 i 
            for(int k=min(K, j); k>=1; k--) //理论上 k也需要从大到小，但从小到大也不会错，同样的 k不大于 j 
            {
                f[j][k]=(s1[i]==s2[j])? (f[j-1][k]+g[j-1][k-1])%P: 0; 
                //如果匹配成功就等于上一个 s1[i]匹配 s2[j-1]用 k段的方法数（和这次匹配无关）加上 
                //上一个 s1[i]匹配 s2前 j-1个用 k-1段的方法数总和（相当于是不影响这次匹配的最大方案） 
                g[j][k]=(f[j][k]+g[j][k])%P; //前缀和加上这次的方法数，并 %P 
            }
    printf("%lld\n", g[m][K]);
    return 0;
}