You are given a string *s*. Each pair of numbers *l* and *r* that fulfill the condition 1 ≤ *l* ≤ *r* ≤ |*s*|, correspond to a substring of the string *s*, starting in the position *l* and ending in the position *r* (inclusive).

Let's define the function of two strings *F*(*x*, *y*) like this. We'll find a list of such pairs of numbers for which the corresponding substrings of string *x* are equal to string *y*. Let's sort this list of pairs according to the pair's first number's increasing. The value of function *F*(*x*, *y*) equals the number of non-empty continuous sequences in the list.

For example: *F*(*babbabbababbab*, *babb*) = 6. The list of pairs is as follows:

(1, 4), (4, 7), (9, 12)

Its continuous sequences are: 
 -  (1, 4) -  (4, 7) -  (9, 12) -  (1, 4), (4, 7) -  (4, 7), (9, 12) -  (1, 4), (4, 7), (9, 12) 
Your task is to calculate for the given string *s* the sum *F*(*s*, *x*) for all *x*, that *x* belongs to the set of all substrings of a string *s*.
The only line contains the given string *s*, consisting only of small Latin letters (1 ≤ |*s*| ≤ 10<sup class="upper-index">5</sup>).
aaaa
20
abcdef
21
abacabadabacaba
188
tkth
11
eqkrqe
23
cwuiax
21
hhhhqhqh
59
gmxfmcgp
38
eleellleeee
104
usussubuubbbbs
138
lhmpaugvnqzrfxke
136
xkkkkkkkkkkkkkkkkxkkkk
1098
pprppppriiriiiirprppprriir
512
jsoxkutcvyshsinfmtrpujedcbmyqlojzco
646
emcegmekgnlefkeguqkfffnduqhfhhhndlfhlfdqdncefnn
1227
ffffdjfddffdjdfffddjfffffffjfffjdjfffjfjfdjjfjdjjdjjjdffd
2564
cxvhmeyouudwuglhbwndzwmjjsgrnuwnzwaycfspyyrdckjcidfsabvdxzjkvm
2023
cahdktuxuukmbuqcqactqhqdcxpkqcuumckttdpmpqxxkacpappxuqkxbuahqdphhddhquthqaapm
3258
hhwhhwhhhwhwwhhwwwhwhhhwhwwwhhwhwhhhhhhwhwhwwwhhwwwhhwhhhhwhwwhwhwwwwhhwwhwhwwwhhhwwhwhwhhwwwhwhhhwwwhwhw
10856
cnrkvxbljhitbvoysdpghhhnymktvburpvxybnvugkzudmnmpuhevzyjpbtraaepszhhssmcozkgbjayztrvqwdfmjlhtvarkkdsbnjrabqexpfjozmjzfbmdsihovoxmmtjgtfyaisllysnekdxozhdwu
12399
qasiyhdivaiyyhdqiqsvqhtqsetxqvaeqatxesxehisyqiivhvayaxvsxhsydiesaxydysqhedxqhsqivvidqtsitiiveexiehsqdteahyxtsyqetahviyhqvytexethsqssxiytqhxxxdihxietsyxqhtitheyeateeyhythxhhqaad
17103
ggwgwwgwwkggwgwwkgwwwggwwwggkgkgwkwgkkgkwwgwkkggwggkwgwgkgwwkwkkkkwggwwkwkkkgwkwwwwwgwkwkkwkggwwgggkkwwkgkgkwgkgkwggkwgggwwkgkwgkwkkgwkkkkggwwwgkggkwwgkwkgwgggkggkkkwwwwwkkgkwggwgkwwwwggwwgkkggwkkwkkgkwggggggkkwkkgkkkwkwwkwggwkkwggggwg
41166
tmoqyzoikohtgkybnwjizgjypzycmtstmsizrqrmczmqmpewxiwlqzcaufxkchqyjegktxihlksisbgogpyxkltioovelwaqcbebgcyygxsshsirkwvtsvhpqtbomueaszkrlixueyeiccvfiuoogomjlhjkacnxtimkprmjttpmeaminvmcqagrpjighsvaosojymcjoyopsvkrphzbnckcvvckicmjwpvawjuzkofnuvcahwhzjpfngwyobiufivsjnekjcloobvzawrvosnkvalmr
42165
rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrbrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrbrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr
2214420
zzzzooozzzoozozoozzzzzzozooozoozoozzozzozoooozzzzzzoooozzozooozoozzzozozoooooozzzozozooooozozozozzooozozzooozzzzozozoozoozzzozooozzzzoozzzzozzzzoooozozozozozzoooozzzooozzoooooooozozzozozooozzzooooozozooozozzozozoozzozzzzooozzoozozozzozozoozozzzoozozoooozzooozozooooozzzzzoozoozzzozzzoozzoozozzooozzzzzzoozzozzoozzzoozozzooozoozzzozooozozzoozoozozzzzzoozoozzzooooozooooooozooooozzoozoozzzooooozoozozozozzzoozzzzzoozzzzzzooooooozzzzozzozzo
190205
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e5+5;
string a;
struct SAM
{
    int lst=1,tot=1,s=0,siz[maxn<<1];
    vector<int> e[maxn<<1];
    struct node
    {
        int len,fa,ch[30];
    }a[maxn<<1];
    int insert(int c)    
    {
        int p=lst,now=++tot;
        siz[now]=1;
        lst=tot;
        a[now].len=a[p].len+1;
        while(p&&!a[p].ch[c])
            a[p].ch[c]=now,p=a[p].fa;
        if(p==0)
            a[now].fa=1;
        else
        {
            int y=a[p].ch[c];
            if(a[y].len=a[p].len+1)
                a[now].fa=y;
            else
            {
                int x=++tot;
                a[x].len=a[p].len+1;
                a[x].fa=a[y].fa;
                a[now].fa=a[y].fa=x;
                for(int i=1;i<=26;i++)
                    a[x].ch[i]=a[y].ch[i];
                while(p&&a[p].ch[c]==y)
                    a[p].ch[c]=x,p=a[p].fa;
            }
        }
    }
    void dfs(int x)
    {
        for(auto v:e[x])
        {
            dfs(v);
            siz[x]+=siz[v];
        }
        s+=(a[x].len-a[a[x].fa].len)*(siz[x])*(siz[x]+1)/2;
        // cout<<x<<' '<<siz[x]<<endl;
    }
    void calc()
    {
        // for(int i=2;i<=tot;i++)
        //     cout<<a[i].fa<<' ';
        // puts("");
        for(int i=2;i<=tot;i++)
            e[a[i].fa].push_back(i);
        dfs(1);       
    }

}s;
signed main()
{
    cin>>a;
    for(auto i:a)
        s.insert(i);
    s.calc();
    cout<<s.s<<endl;
    return 0;
}