6 3 1

aabaab

aab

2

6 3 2

aabaab

aab

7

6 3 3

aabaab

aab

7

/*

    很明显，这是一道dp题，然后来想想怎么表示状态,对答案有影响的就是A串的第i个字符，B串的第j个字符，和k个子串,简单来说就是和选取的字符和子串的数量有关.那么设f[i][j][kk]表示在A串的前i个字符中选kk个子串匹配B串的前j个字符的方案数.求方案数可以采用加法原理，考虑A串的第i个字符,那么这个字符的决策只有取或不取，很明显，加法原理，把不取的方案数和取的方案数加起来就可以，但是状态的定义并不能看出这个字符到底取不取，或者说并不能推出结果来，怎么办呢？

    那么就用一个数组s[i][j][kk]来表示在A串的前i个字符中选kk个子串匹配B串的前j个字符的方案数，A串的第i个字符会被取到.那么这个s数组该怎么推出来呢？可以发现，如果取第i个字符也有2种可能，因为kk是一定的，第i个字符可能和第i-1个字符合并成一个子串，那么从s[i-1][j][kk]转移过来，也可能不和第i-1个字符合并成一个子串，那么就要新开一个子串，故kk一定从kk-1转移过来，根据加法原理，那么s[i][j][kk] = s[i-1][j-1][kk] + f[i-1][j-1][kk-1].

    还有一个问题，f数组该怎么推呢？根据之前分析的，把不取和取的加上来即可,即f[i][j][kk] = s[i][j][kk] + f[i-1][j][kk],其实可以发现，f数组就相当于前缀和数组.

    还有一个问题：这是一个三维的状态转移方程！空间不一定开的下，再看数据范围，这绝对MLE,怎么办?注意到i只能从i或i-1转移过来，可以想到滚动数组，滚动数组有一个比较好些的写法就是把第一维全部加上&1,或者干脆弄两个变量处理完一组数据就交换即可.

*/

#include<iostream>

#include<cstdio>

#define mod 1000000007

using namespace std;

int len1,len2,f[][][],s[][][],n;

char s1[],s2[];

int main(){

    scanf("%d%d%d%s%s",&len1,&len2,&n,s1+,s2+);

    f[][][]=;

    for(int i=;i<=len1;i++){

        f[i&][][]=;

        for(int j=;j<=len2;j++){

            for(int k=;k<=n;k++){

                if(s1[i]==s2[j])

                s[i&][j][k]=(s[(i-)&][j-][k]+f[(i-)&][j-][k-])%mod;

                else

                s[i&][j][k]=;

                f[i&][j][k]=(f[(i-)&][j][k]+s[i&][j][k])%mod;

            }

        }

    }

    printf("%d",f[len1&][len2][n]);

}

P2680 运输计划