#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define p_b push_back using namespace std; typedef long long ll; const int maxn=5e5+10,mod=1e9+7; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int n;string s; int rk[maxn],sa[maxn],cnt[maxn],tmp[maxn],height[maxn]; vector<int>P[150]; void SA(){ reverse(s.begin()+1,s.end()); up(i,1,n)P[s[i]].p_b(i);int c=0; up(i,1,149)if(P[i].size()){++c; for(int x:P[i])rk[x]=c; } for(int k=1;k<n;k<<=1){ up(i,0,n)cnt[i]=0; up(i,1,n)cnt[rk[i+k]]++; up(i,1,n)cnt[i]+=cnt[i-1]; up(i,1,n)tmp[cnt[rk[i+k]]--]=i; up(i,0,n)cnt[i]=0; up(i,1,n)cnt[rk[i]]++; up(i,1,n)cnt[i]+=cnt[i-1]; down(i,n,1){int p=tmp[i];sa[cnt[rk[p]]--]=p;} up(i,1,n)tmp[i]=rk[i];int u=0; up(i,1,n)u+=tmp[sa[i]]!=tmp[sa[i-1]]||tmp[sa[i]+k]!=tmp[sa[i-1]+k],rk[sa[i]]=u; } up(i,1,n){ if(rk[i]==1)continue; height[rk[i]]=max(height[rk[i-1]]-1,0); while(s[i+height[rk[i]]]==s[sa[rk[i]-1]+height[rk[i]]])++height[rk[i]]; } up(i,1,n)sa[i]=n+1-sa[i]; reverse(rk+1,rk+n+1); } struct SegTree { int h[maxn]; struct nd { int mn;ll sm,len; }d[maxn<<2]; #define ls(p) (p<<1) #define rs(p) (p<<1|1) ll ask(int s,int t,int p,int k){ if(s==t)return min(d[p].mn,k)*d[p].len; int mid=s+t>>1; if(d[ls(p)].mn<k)return ask(s,mid,ls(p),k)+d[p].sm-d[ls(p)].sm; return ask(mid+1,t,rs(p),k)+d[ls(p)].len*1ll*k; } void pu(int s,int t,int p){ int mid=s+t>>1; d[p].mn=min(d[ls(p)].mn,d[rs(p)].mn); d[p].sm=d[ls(p)].sm+ask(mid+1,t,rs(p),d[ls(p)].mn); d[p].len=d[ls(p)].len+d[rs(p)].len; } void bd(int l,int r,int p){ if(l==r)return d[p].mn=h[l],void(); int mid=l+r>>1; bd(l,mid,ls(p)),bd(mid+1,r,rs(p));pu(l,r,p); } void modify(int l,int s,int t,int p,int k){ if(s==t)return d[p].len++,d[p].sm+=k,void(); int mid=s+t>>1; if(l<=mid)modify(l,s,mid,ls(p),k);else modify(l,mid+1,t,rs(p),k);pu(s,t,p); } ll ask(int l,int r,int s,int t,int p,int& k){ if(l<=s&&t<=r){ll ans=ask(s,t,p,k);k=min(k,d[p].mn);return ans;} int mid=s+t>>1;ll res=0; if(l<=mid)res+=ask(l,r,s,mid,ls(p),k);if(r>mid)res+=ask(l,r,mid+1,t,rs(p),k); return res; } }A,B; void slv(){ n=read();cin>>s;s=" "+s;SA(); up(i,2,n)A.h[i]=height[i],B.h[i]=height[n+2-i]; A.bd(2,n,1),B.bd(2,n,1); ll res=0,ans=0; up(i,1,n){ int k=1e9; if(rk[i]!=n)res+=A.ask(rk[i]+1,n,2,n,1,k); k=1e9; if(rk[i]!=1)res+=B.ask(n+2-rk[i],n,2,n,1,k); if(rk[i]!=1)A.modify(rk[i],2,n,1,1); if(rk[i]!=n)B.modify(n+2-(rk[i]+1),2,n,1,1); res%=mod,(ans+=res)%=mod; printf("%lld\n",ans); } } int main(){ //freopen("1.in","r",stdin),freopen("1.out","w",stdout); slv(); return 0; }