#include<bits/stdc++.h> #define ll long long using namespace std; const int N=2e5+10,mod=1e9+7; int sa[N],rk[N<<1],ht[N]; string s;int n; int p[N],v[N]; void gsa(){ for(int i=1;i<=n;i++) rk[i]=s[i]-'a'+1; for(int j=0;(1<<j)<=n;j++){ auto cmp=[&](int a,int b){ if(rk[a]==rk[b]) return rk[a+(1<<j)]<rk[b+(1<<j)]; return rk[a]<rk[b]; }; for(int i=1;i<=n;i++) p[i]=i; sort(p+1,p+n+1,cmp); v[1]=1;int nrk=0; for(int i=2;i<=n;i++) v[i]=cmp(p[i-1],p[i]); for(int i=1;i<=n;i++){ nrk+=v[i];rk[p[i]]=nrk; } }for(int i=1;i<=n;i++) sa[rk[i]]=i; int len=0; for(int i=1;i<=n;i++){ if(len) len--; if(rk[i]==1) continue; int pos=sa[rk[i]-1]; for(;s[pos+len]==s[i+len];len++); ht[rk[i]]=len; } } int mn[5050][5050]; int lcp(int a,int b){ int l=rk[a],r=rk[b]; if(l>r) swap(l,r); int ans=mn[l+1][r]; //for(int i=l+1;i<=r;i++) // ans=min(ans,ht[i]); return ans; } int tmp[N]; struct segtree{ struct node{ ll val,sum;int mn; }T[N<<2]; int Leaf[N],len[N<<2]; #define ls p*2 #define rs p*2+1 #define mid (l+r)/2 int calc(int p,int lm){ //if(p==2) cout<<"c:"<<T[ls].val<<' '<<T[rs].mn<<endl; if(len[p]==1) return T[p].sum*min(lm,T[p].mn); if(lm<T[rs].mn){ return T[rs].sum*lm+calc(ls,lm); }else{ return T[p].val+calc(rs,lm); } } void pu(int p){ T[p].val=calc(ls,T[rs].mn); T[p].mn=min(T[ls].mn,T[rs].mn); T[p].sum=T[ls].sum+T[rs].sum; } void bd(int p,int l,int r){ if(l==r){ Leaf[l]=p;T[p].mn=tmp[l]; T[p].val=0;T[p].sum=0;len[p]=1; return ; }bd(ls,l,mid);bd(rs,mid+1,r);pu(p); len[p]=len[ls]+len[rs]; } void upd(int p,int l,int r,int x){ if(l==r){ T[p].sum=1,T[p].val=T[p].mn; return ; } if(x<=mid) upd(ls,l,mid,x); else upd(rs,mid+1,r,x);pu(p); } int qry(int x){ x=Leaf[x];if(!x) return 0; ll res=T[x].val;int mn=T[x].mn; bool fl=(x==Leaf[6]); while(x!=1){ if(x&1){ res+=calc(x^1,mn); //if(fl) cout<<"calc:"<<x<<' '<<mn<<' '<<res<<endl; mn=min(mn,T[x^1].mn); }x>>=1; }return res%mod; } }pre,suf; int ans[N]; int main(){ cin>>n;cin>>s; reverse(s.begin(),s.end()); s=' '+s+' ';gsa(); //for(int i=1;i<=n;i++) cout<<rk[i]<<' ';cout<<endl; for(int i=1;i<=n;i++) tmp[i]=ht[i]; pre.bd(1,1,n);//updLqryR for(int i=1;i<=n;i++) tmp[i]=ht[n+1-i]; suf.bd(1,1,n);//updRqryL for(int i=n;i>=1;i--){ int p=rk[i]; //cout<<p<<endl; //for(int j=1;j<=n;j++) cout<<ht[j]<<' ';cout<<endl; ans[i]+=pre.qry(p); //cout<<ans[i]<<' '; ans[i]+=suf.qry(n+1-(p+1)); ans[i]%=mod; //cout<<ans[i]<<endl; pre.upd(1,1,n,p+1); suf.upd(1,1,n,n+1-p); } for(int i=n;i>=1;i--) ans[i]=(ans[i]+ans[i+1])%mod; for(int i=n;i>=1;i--) ans[i]=(ans[i]+ans[i+1])%mod; for(int i=n;i>=1;i--) cout<<ans[i]<<endl; return 0; }