Pair of Strings - CRANPAIR - Cranium 2015

/*  Sanchit Abrol  */
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define mp make_pair
#define all(X) (X).begin(),(X).end()
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define s(a) scanf("%d", &a)

int N,i,j,T,k,ans[5010*5010];
char a[5010], b[5010];
long long MOD = 1000000007;

int main()
{
    s(N);
    s(k);
    scanf("%s", a);
    scanf("%s", b);
    for(i = 0; i+k-1 < N; i++)
    {
        int st = (N-k+1) * i;
        int ap = i, bp = 0, c = 0;
        for(j = 0; j < k; j++, ap++, bp++)
            c += (a[ap] == b[bp]);
        ans[st] = c;
        while(ap < N)
        {
            c = c - (a[ap-k] == b[bp-k]) + (a[ap] == b[bp]);
            st += N-k+2;
            ans[st] = c;
            ap++; bp++;
        }
    }
    for(i = 1; i+k-1 < N; i++)
    {
        int st = i;
        int ap = 0, bp = i, c = 0;
        for(j = 0; j < k; j++, ap++, bp++)
            c += (a[ap] == b[bp]);
        ans[st] = c;
        while(bp < N)
        {
            c = c - (a[ap-k] == b[bp-k]) + (a[ap] == b[bp]);
            st += N-k+2;
            ans[st] = c;
            ap++; bp++;
        }
    }
    int x = (N - k + 1) * (N - k + 1);
    long long fans = 0;
    for(i = 0; i < x; i++)
    {
        fans += ((long long)ans[i] * (i+1)) % MOD;
        if(fans >= MOD)
            fans -= MOD;
    }
    printf("%lld\n", fans);

    return 0;
}