int recurse(int in, int maximumMatchingPrefixLength, int n, int m, int numberOfRequiredSubString) {
    if(in == n) {
        return numberOfRequiredSubString > 0;
    }

    int ans = 0;

    // matching case
    if(maximumMatchingPrefixLength+1 >= m) {
        // insert the last character, and now maximum matching prefix would become 0
        // and number of required substring would increase by 1
        ans += recurse(in+1, 0, n, m, numberOfRequiredSubString+1);
    }
    else {
        // insert that character, which is matching to next character after maximum matching prefix
        // for ex, required substring = ABC
        // and current string is XGAB
        // then, we are inserting C here
        ans += recurse(in+1, maximumMatchingPrefixLength+1, n, m, numberOfRequiredSubString);
    }

    // non matching case
    // insert all those characters, which are coming after any prefix length of Required string
    // and recurse for next position, with that prefix length
    set<char> uc;
    uc.insert(s[maximumMatchingPrefixLength]);
    maximumMatchingPrefixLength = lps[maximumMatchingPrefixLength - 1];
    while(maximumMatchingPrefixLength > 0) {
        uc.insert(s[maximumMatchingPrefixLength]);
        ans += recurse(in+1, lps[maximumMatchingPrefixLength-1], n, m, numberOfRequiredSubString);
        maximumMatchingPrefixLength = lps[maximumMatchingPrefixLength-1];
    }    
    
    // insert other characters, which did not come till now
    ans += (26 - uc.size()) * recurse(in+1, 0, n, m, numberOfRequiredSubString);

    return ans;

}

ll solve(int i, int n, int j, string &s)
{
    if(done[i][j]) return dp[i][j];
    done[i][j] = true;
    if(i == n) return dp[i][j] = (j==(int)s.size()?1:0);
    if(j == (int)s.size())
    {
        return dp[i][j] = (mxK*solve(i+1,n,j,s))%mod;
    }
    ll ans = 0;
    int t;
    for(int k = 0; k < mxK; k++)
    {
        t = j;
        while(true)
        {
            if(k == s[t]-'A')
            {
                t++;
                break;
            }
            else if(t)
            {
                t = kmp[t-1];
            }
            else break;
        }
        ans += solve(i+1,n,t,s);
        ans %= mod;
    }
    return dp[i][j] = ans;
}