小猿的打字机

//参考内容https://segmentfault.com/a/1190000021780192 //动态规划递推公式 #include<iostream>
(720)#include<vector>
#include<queue>
(789)#include<string>
#include<functional>
(1307)#define LL long long
using namespace std;
int main() {
    LL n, m, k;
    cin >> n >> m >> k;
    string s1, s2;
    cin >> s1 >> s2;
    int cnt = 0;
    for (int i = 0; i < n; i++)
    {
        if (s1[i] == s2[i])cnt++;
    }
    if (k == 0)
    {
        if (s1.compare(s2) == 0)
            cout << "1" << endl;
        else cout << "0" << endl;
        return 0;
    }
    int mod = 1e9 + 7;
    vector<vector<LL>>C(n + 1, vector<LL>(n + 1, 0));
    vector<vector<LL>>change(n + 1, vector<LL>(n + 1, 0));//the coefficient of change[a-i+j] to change[a]
    //change用来记录系数
        //C[n][m]为组合数， C(n, m)
        //mi[n] = 1<<n-1;
        vector<LL>mi;
    mi.push_back(1);
    for (int i = 0; i <= k; i++)
    {
        mi.push_back(mi.back() % mod << 1);
        //cout << mi.back() << endl;
    }
    for (int i = 0; i < n + 1; i++)
        C[i][0] = 1;
    for (int i = 1; i < n + 1; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
            C[i][j] %= mod;
        }
    }
    for (int a = 0; a <= n; a++)
    {
        for (int i = 0; i <= k; i++)
        {
            int tmp = mi[i] * C[a][i] % mod * C[n - a][k - i] % mod;
            for (int j = 0; j <= k - i; j++)
            {
                if (a - i + j >= 0 && a - i + j <= n)
                    change[a][a - i + j] = (tmp*C[k - i][j]+change[a][a - i + j]) % mod;
            }
        }
    }
    vector<int>ans(n + 1, 0), mm;//由于每一次快捷操作只和上一次结果有关，故降至一维
    ans[n] = 1;
    while (m--)
    {
        mm.clear();
        for (int i = 0; i <= n; i++)
        {
            int tmp = 0;
            for (int j = 0; j <= n; j++)
            {
                tmp = (change[i][j] * ans[j]+tmp) % mod;
            }
            mm.push_back(tmp);
        }
        ans = mm;
    }

    cout << ans[cnt] << endl;
}