#include
using namespace std;
typedef long long dint; #ifdef WIN32 #define lld “%I64d” #else #define lld “%lld” #endif #define _l (long long int)
struct node { int l, i, ri; node *tr[26], *pr; node() { ri = l = 0; memset(tr, 0, sizeof(tr)); } }; struct edge { int t; edge *next; };
const int maxn = 1000009;
char a[maxn]; int n, ni, f[maxn], sz[maxn], d[maxn]; dint ans; edge ebuf_arr[maxn], *ebuf(ebuf_arr), *head[maxn]; node nbuf_arr[maxn], *nbuf(nbuf_arr), *l, *srt, *scur;
void samIns(int w) { node *p, *np(nbuf ++); np-> i = ++ ni; np-> l = scur-> l + 1; for (p = scur; p && !p-> tr[w]; p = p-> pr) p-> tr[w] = np; if (p) { node *q(p-> tr[w]); if (q-> l != p-> l + 1) { node *nq(nbuf ++); memcpy(nq, q, sizeof(node)); nq-> ri = 0; nq-> i = ++ ni; nq-> l = p-> l + 1; np-> pr = q-> pr = nq; for (; p && p-> tr[w] == q; p = p-> pr) p-> tr[w] = nq; } else np-> pr = q; } else np-> pr = srt; ++ np-> ri; scur = np; }
inline void addEdge(int u, int v) { ebuf-> t = v; ebuf-> next = head[u]; head[u] = ebuf ++; }
dint dp() { dint s(0); static int q[maxn]; int hd(0), tl(1); d[q[0] = srt-> i] = 0; while (hd < tl) { int p(q[hd ++]); for (edge* e = head[p]; e; e = e-> next) { //d[e-> t] = d[p] + 1; q[tl ++] = e-> t; } } for (int i = tl - 1; i >= 0; – i) { int p(q[i]); for (edge* e = head[p]; e; e = e-> next) { s += _l sz[e-> t] * sz[p] * d[p]; sz[p] += sz[e-> t]; } } return s; }
int main() { #ifndef ONLINE_JUDGE freopen(".in", “r”, stdin); #endif
scanf("%s", a);
n = strlen(a);
srt = scur = nbuf ++;
srt-> i = ni = 1;
srt-> pr = 0;
for (int i = n - 1; i >= 0; -- i)
samIns(a[i] - 97);
memset(head, 0, sizeof(head));
for (node *i = srt; i != nbuf; ++ i) {
d[i-> i] = i-> l;
sz[i-> i] = i-> ri;
if (i-> pr)
addEdge(i-> pr-> i, i-> i);
}
ans = _l n * (n - 1) * (n + 1) / 2 - dp() * 2;
printf(lld "\n", ans);
}