#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 5000010
#define mod 19930726
char a[MAXN],b[MAXN];
ll d[MAXN],cnt[MAXN];
ll n,l,r,k,maxz,ans=1,num;
ll ksm(ll ds,ll zs){
    ll ansz=1;
    while(zs){
        if(zs%2==1)ansz=(ansz*ds)%mod;
        ds=(ds*ds)%mod;
        zs/=2;
    }
    return ansz%mod;
}
int main(){
    freopen("rehearse.in","r",stdin);
    freopen("rehearse.out","w",stdout);
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        b[i*2]=a[i];
        b[i*2-1]='#';
    }
    l=0,r=0;
    a[0]='!';
    for(int i=1;i<=n*2;i++){
        if(i<=r){
            int p=r-i+l;
            if(d[p]<r-i+1)d[i]=d[p];
            else{
                d[i]=r-i+1;
                while(b[i-d[i]]==b[i+d[i]])d[i]++;
            }
        }else{
            while(b[i-d[i]]==b[i+d[i]])d[i]++;
        }
        if(r<i+d[i]-1){
            r=i+d[i]-1;
            l=i-d[i]+1;
        }
        if(b[i]!='#'){
            ll p=((d[i]+1)/2)*2-1;
            cnt[p]++;
            maxz=max(maxz,p);
        }
    }
    for(int i=maxz;i;i--){
        cnt[i-2]+=cnt[i];
        num=cnt[i];
//        cout<<i<<" "<<num<<endl;
        if(k>num){
            ans=(ans*ksm(i,num))%mod;
            k-=cnt[i];
        }else{
            ans=(ans*ksm(i,k))%mod;
            k=0;
            break;
        }
    }
    if(k)cout<<"-1";
    else cout<<ans%mod;
//    for(int i=1;i<=2*n;i++)cout<<b[i]<<" ";
//    cout<<endl;
//    for(int i=1;i<=2*n;i++){
//        cout<<d[i]<<" ";
//    }
    return 0;
}