rt，试了好多写法（包括但不限于 vector 存图）都会 mle on 14,16,18,20。

但感觉自己应该没啥特别爆空间的地方吧

#include<cstdio>
const int mod=1e9+7;
int n,m,a[1000001],fail[1000001];
int dp[1000001],h[1000001],dps[1000001];
int lps[101],svd[1000001];
int hed[1000001],net[1000001],ver[1000001],tot;
void add(int x,int y){
	ver[++tot]=y;
	net[tot]=hed[x];
	hed[x]=tot;
}
void dfs(int x){
	svd[x]=lps[a[x+1]];
	lps[a[x+1]]=x;
	for(int i=hed[x];i;i=net[i]){
		dps[ver[i]]=lps[a[ver[i]+1]];
		dfs(ver[i]);
	}
	lps[a[x+1]]=svd[x];
}
int main(){
	int i,j=0;
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)scanf("%d",&a[i]);
	for(i=2;i<=m;i++){
		while(j&&a[j+1]!=a[i])j=fail[j];
		if(a[j+1]==a[i])j++;
		fail[i]=j;
	}
	for(i=1;i<m;i++)add(fail[i],i); 
	for(i=1;i<=n;i++)lps[i]=-1;
	dfs(0);
	dp[0]=h[0]=n;
	for(i=1;i<m;i++){
		dp[i]=n+1ll*(n-1)*dp[i-1]%mod;dp[i]%=mod;
		h[i]=h[fail[i]];
		if(dps[i]!=-1)h[i]+=mod-dp[dps[i]],h[i]%=mod;
		dp[i]+=mod-h[i];dp[i]%=mod;
		dp[i]+=dp[i-1];dp[i]%=mod;
		h[i]+=dp[i];h[i]%=mod;
	}
	for(i=1;i<=m;i++)printf("%d\n",dp[i-1]);
}