60求，壶关

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7,N=1010,M=210;
int dp[2][M][M][2];
char st1[N],st2[N];
int n,m,k;
int main()
{
	
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++) cin>>st1[i];
	for(int i=1;i<=m;i++) cin>>st2[i];
	dp[0][0][0][0]=1;
	dp[1][0][0][0]=1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			for(int p=1;p<=k;p++)
			{
				if(st1[i]==st2[j])
				{
					dp[i%2][j][p][1]=(dp[(i-1)%2][j-1][p][1]+dp[(i-1)%2][j-1][p-1][0]+dp[(i-1)%2][j-1][p-1][1])%mod;
					dp[i%2][j][p][0]=(dp[(i-1)%2][j][p][1]+dp[(i-1)%2][j][p][0])%mod;
				}
				else
				{
					dp[i%2][j][p][0]=(dp[(i-1)%2][j][p][1]+dp[(i-1)%2][j][p][0])%mod;
					dp[i%2][j][p][1]=0;
				}
			}
	cout<<(dp[n%2][m][k][1]+dp[n%2][m][k][0])%mod;
	return 0;
}