#include<cstdio>
#include<cstring>
#define LL long long char st[],stt[];
LL ans;
int leafr,ndcnt=,sidcnt,lastcre;
int isleaf[],dep[],nd[],l[],r[],des[],
next[],sufchain[]; int getr(int sid){
if (isleaf[des[sid]]) return(leafr);else return(r[sid]);
} void cut(int po,int sid,int len){
dep[++ndcnt]=dep[po]+len;
isleaf[ndcnt]=; nd[ndcnt]=++sidcnt;
des[sidcnt]=des[sid];
l[sidcnt]=len+l[sid];r[sidcnt]=getr(sid);next[sidcnt]=-;des[sidcnt]=des[sid];
des[sid]=ndcnt;r[sid]=len+l[sid]-;
} void ins(int po,int alph){
dep[++ndcnt]=dep[po]+;
isleaf[ndcnt]=;
nd[ndcnt]=-; l[++sidcnt]=alph;r[sidcnt]=alph;
des[sidcnt]=ndcnt;next[sidcnt]=nd[po];nd[po]=sidcnt;
} void buildtree(){
int po=,lastins=;nd[]=-;sufchain[]=;int prom=; for (int i=;i<=strlen(st)-;i++){
leafr=i;int p,flag;
prom=; while (lastins<=i){ while(){
flag=;
for (p=nd[po];p!=-;p=next[p])
if (st[l[p]]==st[lastins+dep[po]]) break; if (p==-){ins(po,i);
if (prom) sufchain[lastcre]=po;
prom=;
lastcre=po;
break;}
if (i-lastins+-dep[po]<=getr(p)-l[p]+){
if (st[i]==st[l[p]+i-lastins-dep[po]])
{flag=;
if (prom) sufchain[lastcre]=po;
prom=;
lastcre=po;
break;}
if (st[i]!=st[l[p]+i-lastins-dep[po]]) {
cut(po,p,i-lastins-dep[po]);
if (prom) sufchain[lastcre]=ndcnt;
if (i-lastins-dep[po]>) prom=;else prom=;
lastcre=ndcnt;sufchain[lastcre]=;
ins(ndcnt,i);break;
}
}
if (i-lastins+-dep[po]>getr(p)-l[p]+) po=des[p];
}
if (flag) {break;}
po=sufchain[po];lastins++;
}
}
} int top=;
struct str{
int po,fr;
LL cnt,len;
}sta[]; void pb(int ps,int le,int p){
sta[++top].po=p;sta[top].len=le;sta[top].fr=ps;
sta[top].cnt=;
} void pop(){
if (isleaf[sta[top].po]) sta[top].cnt++;
sta[sta[top].fr].cnt+=sta[top].cnt;
top--;
} void getans(){
pb(,,);top=; int i=;
while (top>=i){
int tp=i;
for (int p=nd[sta[tp].po];p!=-;p=next[p])
pb(tp,getr(p)-l[p]+,des[p]);
i++;
} while(top){
ans-=sta[top].len*sta[top].cnt*(sta[top].cnt-);
pop();
}
} int main(){
scanf("%s",stt); LL len=strlen(stt);ans=(len-)*len*(len+)/; st[]=' ';
strcat(stt,"$");strcat(st,stt); buildtree(); getans(); printf("%lld",ans);
}
注意某一个串对应点到后缀树根的深度是$O(n \cdot \sqrt{n})$的