BZ4175-DP

#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 N=4e5+7;

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

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[2][N];

    inline void solve(int n,int m){
        f[0][0]=1;
        for(int i=1;i<=n;++i){
            for(int j=0;j<=m;++j)f[i&1][j]=0;
            for(int j=m;j;--j){
                for(int k=2;k<=tot;++k){
                    if(j>=siz[k]){
                        f[i&1][j]=add(f[i&1][j],(ll)f[i&1^1][j-siz[k]]*(len[k]-len[fa[k]])%p*siz[k]%p);
                    }
                }
            }
        }
        printf("%d\n",f[n&1][m]);
        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);
}