#include<bits/stdc++.h>
#define int long long
using namespace std;
//#define fin cin
//#define fout cout
ifstream fin("rehearse.in");
ofstream fout("rehearse.out");
auto mread = [](){
    int x;
    fin >> x;
    return x;
};
const int N = 1e6 + 5, MOD = 19930726;
int n = mread(), k = mread(), sum[N], ans = 1, r[N];
string s;
int ksm(int x, int k){
    int ans = 1, now = x;
    while(k){
        if(k & 1)
        ans = ans * now % MOD;
        now = now * now % MOD;
        k >>= 1;
    }
    return ans;
}
signed main(){
    fin >> s;
    r[0] = 1;
    int p = 0, ma = 0;
    for(int i = 1; i < n; i ++){
        if(ma >= i){
            int t = p - (i - p + 1) + 1;
            r[i] = min(ma - i + 1, r[t]);
        }
        else{
            r[i] = 1;
        }
        while(i - r[i] >= 0 && i + r[i] <= n && s[i - r[i]] == s[i + r[i]]){
            r[i] ++;
        }
        if(i + r[i] - 1 >= ma){
            ma = i + r[i] - 1;
            p = i;
        }
        sum[r[i] + r[i] - 1] ++;
    }
    for(int i = (n % 2 ? n : n - 1); i >= 3 && k; i -= 2){
        if(sum[i]){
            int tmp = min(sum[i], k);
            k -= tmp;
            sum[i - 2] += tmp;
            ans = ans * ksm(i, tmp) % MOD;
        }
    }
    fout << ans;
    return 0;
}