全新题解（真的没抄）

#include <iostream>
#include <cstring>
using namespace std;

const int MOD = 1000000007;
const int MAXN = 1005;
const int MAXM = 205;

int n, m, k;
char A[MAXN], B[MAXM];
int dp[2][MAXM][MAXM][2]; // 使用滚动数组优化空间

int main() {
cin >> n >> m >> k;
cin >> (A + 1) >> (B + 1); // 从1开始索引

dp[0][0][0][0] = 1;
for (int i = 1; i <= n; i++) {
    int cur = i % 2, prev = 1 - cur;
    memset(dp[cur], 0, sizeof(dp[cur]));
    
    for (int j = 0; j <= m; j++) {
        for (int t = 0; t <= k; t++) {
            // 不选A[i]的情况
            dp[cur][j][t][0] = (dp[prev][j][t][0] + dp[prev][j][t][1]) % MOD;
            
            // 选A[i]的情况
            if (j > 0 && t > 0 && A[i] == B[j]) {
                dp[cur][j][t][1] = dp[prev][j-1][t][1]; // 延续上一个子串
                if (t > 0) {
                    dp[cur][j][t][1] = (dp[cur][j][t][1] + 
                                       dp[prev][j-1][t-1][0]) % MOD; // 新开一个子串
                    dp[cur][j][t][1] = (dp[cur][j][t][1] + 
                                       dp[prev][j-1][t-1][1]) % MOD;
                }
            }
        }
    }
}

int ans = (dp[n%2][m][k][0] + dp[n%2][m][k][1]) % MOD;
cout << ans << endl;

return 0;

}