记录编号	616310	评测结果	AAAAAAAAAA
题目名称	[NOIP 2015]子串	最终得分	100
用户昵称	终焉折枝	是否通过	通过
代码语言	C++	运行时间	0.126 s
提交时间	2026-06-12 09:25:36	内存使用	3.79 MiB

//#pragma GCC optimize(3)
//#pragma GCC target("avx")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("inline")
//#pragma GCC optimize("-fgcse")
//#pragma GCC optimize("-fgcse-lm")
//#pragma GCC optimize("-fipa-sra")
//#pragma GCC optimize("-ftree-pre")
//#pragma GCC optimize("-ftree-vrp")
//#pragma GCC optimize("-fpeephole2")
//#pragma GCC optimize("-ffast-math")
//#pragma GCC optimize("-fsched-spec")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-falign-jumps")
//#pragma GCC optimize("-falign-loops")
//#pragma GCC optimize("-falign-labels")
//#pragma GCC optimize("-fdevirtualize")
//#pragma GCC optimize("-fcaller-saves")
//#pragma GCC optimize("-fcrossjumping")
//#pragma GCC optimize("-fthread-jumps")
//#pragma GCC optimize("-funroll-loops")
//#pragma GCC optimize("-fwhole-program")
//#pragma GCC optimize("-freorder-blocks")
//#pragma GCC optimize("-fschedule-insns")
//#pragma GCC optimize("inline-functions")
//#pragma GCC optimize("-ftree-tail-merge")
//#pragma GCC optimize("-fschedule-insns2")
//#pragma GCC optimize("-fstrict-aliasing")
//#pragma GCC optimize("-fstrict-overflow")
//#pragma GCC optimize("-falign-functions")
//#pragma GCC optimize("-fcse-skip-blocks")
//#pragma GCC optimize("-fcse-follow-jumps")
//#pragma GCC optimize("-fsched-interblock")
//#pragma GCC optimize("-fpartial-inlining")
//#pragma GCC optimize("no-stack-protector")
//#pragma GCC optimize("-freorder-functions")
//#pragma GCC optimize("-findirect-inlining")
//#pragma GCC optimize("-fhoist-adjacent-loads")
//#pragma GCC optimize("-frerun-cse-after-loop")
//#pragma GCC optimize("inline-small-functions")
//#pragma GCC optimize("-finline-small-functions")
//#pragma GCC optimize("-ftree-switch-conversion")
//#pragma GCC optimize("-foptimize-sibling-calls")
//#pragma GCC optimize("-fexpensive-optimizations")
//#pragma GCC optimize("-funsafe-loop-optimizations")
//#pragma GCC optimize("inline-functions-called-once")
//#pragma GCC optimize("-fdelete-null-pointer-checks")
//#pragma GCC optimize(2)
#include<iostream>
#include<algorithm>
#include<set>
#include<map>
#include<unordered_map>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<stdio.h>
#include<stdlib.h>
#include<string>
#include<typeinfo>
#define ll long long
#define ull usigned long long
using namespace std;
namespace M{
    template<typename T>
    inline T min(T a, T b){return a < b ? a : b;}
    template<typename T>
    inline T max(T a, T b){return a > b ? a : b;}
    template<typename T>
    inline T abs(T x){return x < 0 ? -x : x; }
    template<typename T>
    inline void swap(T &a, T &b){T x = a; a = b, b = x;}
    template<typename T>
    inline T gcd(T a, T b){return b == 0 ? a : gcd(b, a % b);}
    template<typename T>
    inline T lcm(T a, T b){return (a / gcd(a, b)) * b;}
    template<typename T>
    inline T pow(T x, T n){
        T res = 1;
        while(n){
            if(n & 1) res = res * x;
            n >>= 1; x = x * x;
        }
        return res;
    }
    template<typename T>
    inline T pow(T x, T n, const T Mode){
        T res = 1;
        while(n){
            if(n & 1) res = (res * x) % Mode;
            n >>= 1;
			x = (x * x) % Mode;
        }
        return res % Mode;
    }
}

const int N = 1e3 + 5;
const int MM = 202 + 5;
int f[MM][MM];
//f[i][j][k] 表示选择第 i 位，且选 k 个子串，匹配模式串的前 j 个字符
int g[MM][MM];
//g[i][j][k] 表示前缀的方案数，选择了 k 个字串，匹配前 j 个字符
int n, m, K;
char a[N], b[N];
const int P = 1e9 + 7;

int main(){
	cin >> n >> m >> K;
	cin >> (a + 1);
	cin >> (b + 1);
	f[0][0] = 1;
	g[0][0] = 1;
	for(int i = 1;i <= n;i ++){
		for(int j = m;j >= 1;j --){
			for(int k = K;k >= 1;k --){
				if(a[i] == b[j]){
					f[j][k] = (g[j - 1][k - 1] + f[j - 1][k]) % P;
					g[j][k] = (g[j][k] + f[j][k]) % P;
				}
				else{
					f[j][k] = 0;
					g[j][k] = g[j][k];
				}
			}
		}
	}
	cout << g[m][K] << '\n';
	return 0;
}