思路大概如下：

考虑dp[i][j][k]（这个k不是题目中的k，题目中的k用p表示）表示 以A字符串中的第i位作为末尾匹配到B中第j位用了k个子串的方案数（如果a[i]与b[j]不匹配则dp[i][j][k]=0）。 (代码中为了方便初始化把k放到了第一维)

方程大概如下：

然后发现这个可以前缀和优化，然后k可以滚动数组滚掉，然后初始化为$dp[0][0][0]=1$

代码如下：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
typedef unsigned int UI;
typedef pair <int, int> pi;
#define MOD 1000000007
template <typename T>
inline void read(T &x){
    x = 0;int fu = 1;
    char c = getchar();
    while(c > 57 || c < 48){
        if(c == 45) fu = -1;
        c = getchar();
    }
    while(c <= 57 && c >= 48){
        x = (x << 3) + (x << 1) + c - 48;
        c = getchar();
    }
    x *= fu;
}
template <typename T>
inline void fprint(T x){
    if(x < 0) putchar(45), x = -x;
    if(x > 9) fprint(x / 10);
    putchar(x % 10 + 48);
}
template <typename T>
inline void fprint(T x, char ch){
    fprint(x);putchar(ch);
}
char a[1005], b[105];
LL dp[2][1005][105], sig[2][1005][105];
int n, m, p;
int main(){
    // freopen("data.in", "r", stdin);
    // freopen("data.out", "w", stdout);
    read(n);read(m);read(p);
    scanf("%s", a + 1);scanf("%s", b + 1);
    dp[0][0][0] = 1;sig[0][0][0] = 1;
    for (register int i = 1;i <= n;i ++) sig[0][i][0] = 1;
    for (register int k = 1;k <= p;k ++){
        memset(dp[k & 1], 0, sizeof(dp[k & 1]));
        memset(sig[k & 1], 0, sizeof(sig[k & 1]));
        for (register int j = 1;j <= m;j ++){
            for (register int i = 1;i <= n;i ++){
                if(a[i] == b[j]){
                    dp[k & 1][i][j] = (dp[k & 1][i][j] + sig[(k & 1) ^ 1][i - 1][j - 1]) % MOD;
                    dp[k & 1][i][j] = (dp[k & 1][i][j] + dp[k & 1][i - 1][j - 1]) % MOD;
                }
                sig[k & 1][i][j] = (sig[k & 1][i - 1][j] + dp[k & 1][i][j]) % MOD;
                // printf("i = %d, j = %d, k = %d, dp[k][i][j] = %lld\n", i, j, k, dp[k & 1][i][j]);
            }
        }
    }
    fprint(sig[p & 1][n][m], 10);
    return 0;
}