BZ4175-NTT

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)
#define ll long long

template<typename T>
inline void read(T&x){
    T k=1;char gc;x=0;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c))x=x*10+c-'0',gc;x*=k;
}

const int p=1005060097;
const int g=5;
const int N=4e5+7;

inline int add(int a,int b){
    return (a+=b)>=p?a-p:a;
}

inline int sub(int a,int b){
    return (a-=b)<0?a+p:a;
}

inline ll qpow(ll a,ll b){
    ll ans=1;
    while(b){
        if(b&1)(ans*=a)%=p;
        (a*=a)%=p;
        b>>=1;
    }
    return ans;
}

int r[N];
int w1[N];
int w2[N];
inline void DFT(int *A,int n){
    for(int i=0;i<n;++i)if(i<r[i])swap(A[i],A[r[i]]);
    for(int i=1;i<n;i<<=1){
        for(int j=0;j<n;j+=(i<<1)){
            int *w=w1,step=n/i/2;
            for(int k=0;k<i;++k,w+=step){
                int u=A[j+k],v=(ll)A[j+k+i]*(*w)%p;
                A[j+k]=add(u,v);
                A[j+k+i]=sub(u,v);
            }
        }
    }
}

inline void IDFT(int *A,int n){
    for(int i=0;i<n;++i)if(i<r[i])swap(A[i],A[r[i]]);
    for(int i=1;i<n;i<<=1){
        for(int j=0;j<n;j+=(i<<1)){
            int *w=w2,step=n/i/2;
            for(int k=0;k<i;++k,w+=step){
                int u=A[j+k],v=(ll)A[j+k+i]*(*w)%p;
                A[j+k]=add(u,v);
                A[j+k+i]=sub(u,v);
            }
        }
    }
    ll inv=qpow(n,p-2);
    for(int i=0;i<n;++i)A[i]=A[i]*inv%p;
}

struct SAM{
    int tot;
    int len[N],fa[N],to[N][26],siz[N],ord[N],cnt[N];

    inline int NewNode(int l,int *tr,int su){
        ++tot;
        len[tot]=l;
        if(tr!=NULL)memcpy(to[tot],tr,26<<2);
        fa[tot]=su;
        return tot;
    }

    inline int Extend(int u,int c){
        int t=NewNode(len[u]+1,NULL,0);
        for(;u&&!to[u][c];u=fa[u])to[u][c]=t;
        if(!u){
            fa[t]=1;
            return t;
        }
        int v=to[u][c];
        if(len[v]==len[u]+1){
            fa[t]=v;
            return t;
        }
        int x=NewNode(len[u]+1,to[v],fa[v]);
        fa[t]=fa[v]=x;
        for(;u&&to[u][c]==v;u=fa[u])to[u][c]=x;
        return t;
    }

    inline void build(char *s,int n){
        int lst=NewNode(0,NULL,0);
        for(int i=1;i<=n;++i)siz[lst=Extend(lst,s[i]-'a')]=1;
        for(int i=1;i<=tot;++i)cnt[len[i]]++;
        for(int i=1;i<=n;++i)cnt[i]+=cnt[i-1];
        for(int i=1;i<=tot;++i)ord[cnt[len[i]]--]=i;
        for(int i=tot;i>1;--i)siz[fa[ord[i]]]+=siz[ord[i]];
    }

    int F[N];
    int G[N];

    inline void solve(int k,int n){
        ++n;
        for(int i=2;i<=tot;++i){
            if(siz[i]<n){
                F[siz[i]]=add(F[siz[i]],(ll)siz[i]*(len[i]-len[fa[i]])%p);
            }
        }
        G[0]=1;
        int len=1;
        while(len<2*n-1)len<<=1;
        for(int i=0;i<len;++i)r[i]=(r[i>>1]>>1)|((i&1)*(len>>1));
        w1[0]=w2[0]=1;
        w1[1]=qpow(g,(p-1)/len);
        w2[1]=qpow(w1[1],p-2);
        for(int i=2;i<len;++i)w1[i]=(ll)w1[i-1]*w1[1]%p;
        for(int i=2;i<len;++i)w2[i]=(ll)w2[i-1]*w2[1]%p;
        while(k){
            DFT(F,len);
            if(k&1){
                DFT(G,len);
                for(int i=0;i<len;++i)G[i]=(ll)G[i]*F[i]%p;
                IDFT(G,len);
                for(int i=n;i<len;++i)G[i]=0;
            }
            for(int i=0;i<len;++i)F[i]=(ll)F[i]*F[i]%p;
            IDFT(F,len);
            for(int i=n;i<len;++i)F[i]=0;
            k>>=1;
        }
        printf("%d\n",G[--n]);
        return ;
    }
}sam;

char s[N];

int main(){
    freopen("tele.in","r",stdin);
    freopen("tele.out","w",stdout);
    int k,m;r(k),r(m);
    scanf("%s",s+1);
    int n=strlen(s+1);
    sam.build(s,n);
    sam.solve(k,m);
}