考虑拿总方案数减去不合法方案数。一个字符串不合法当且仅当其所有长度为 \(|s|\) 的子串字典序都 \(\ge |s|\)。把这个东西用 KMP 自动机的角度来理解就是假设当前在 KMP 自动机的节点 \(x\)，那么下一步你匹配的字符必须 \(\ge\) \(x\) fail 树上所有祖先节点对应的下一个字符的最大值。
于是问题转化为有多少个字符串 \(t\) 满足 \(|t|=n\) 且将 \(t^{\infty}\) 放在 KMP 自动机上匹配，每一步走的转移边都符合上述要求。
这个 \(t^{\infty}\) 看上去非常鸡肋，考虑着手分析一下这个 \(t^{\infty}\)，显然你再匹配一个 \(t\) 以后它还是 \(t^{\infty}\)，换句话说，假设 \(t^{\infty}\) 对应的节点为 \(x\)，那么从 \(x\) 开始沿着 KMP 自动机依次匹配 \(t\) 中的每个字符，到达的节点还是 \(x\)，而容易证明字符串合法当且仅当从 \(x\) 开始依次匹配 \(t\) 中的每个字符，每一步走的都是合法转移边。
这样我们考虑换个视角：枚举 \(t^{\infty}\) 对应的节点 \(x\)。这样相当于从 \(x\) 开始走 \(n\) 步走回 \(x\)，并且每一步都经过合法转移边的方案数。
朴素 DP 是 \(O(n^3)\) 的。不过容易发现每个节点合法转移边要么指向 \(0\) 要么指向某个不同于 \(0\) 的节点，因此考虑枚举第一次走到 \(0\) 的时刻，DP 预处理 \(dp_{i,j}\) 表示从 \(0\) 开始走 \(i\) 步走到 KMP 自动机上节点 \(j\) 的方案数，就可以做到平方。
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2000;
const int MOD=998244353;
int n,m,nxt[MAXN+5],mx[MAXN+5],dp[MAXN+5][MAXN+5],res,ch[MAXN+5][27];char s[MAXN+5];
void add(int &x,int v){((x+=v)>=MOD)&&(x-=MOD);}
int main(){
scanf("%d%s",&m,s+1);n=strlen(s+1);
for(int i=2,j=0;i<=n;i++){
while(j&&s[j+1]!=s[i])j=nxt[j];
if(s[j+1]==s[i])++j;nxt[i]=j;
}
for(int i=0;i<=n;i++)for(int c=0;c<26;c++){
if(s[i+1]-'a'==c)ch[i][c]=i+1;
else ch[i][c]=ch[nxt[i]][c];
if(ch[i][c])mx[i]=c;
}
dp[0][0]=1;
for(int i=0;i<m;i++)for(int j=0;j<=n;j++)
for(int c=mx[j];c<26;c++)add(dp[i+1][ch[j][c]],dp[i][j]);
for(int i=0;i<=n;i++){
int cur=i;
for(int j=0;j<m;j++){
res=(res+1ll*(26-mx[cur]-1)*dp[m-j-1][i])%MOD;
cur=ch[cur][mx[cur]];if(!cur)break;
}
res=(res+(cur&&cur==i))%MOD;
}
int tot=1;for(int i=1;i<=m;i++)tot=26ll*tot%MOD;
printf("%d\n",(tot-res+MOD)%MOD);
return 0;
}