Problem: 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.

Input

The only line contains the given string s, consisting only of small Latin letters (1 ≤ |s| ≤ 105).

Output

Print the single number — the sought sum.

Please do not use the %lld specificator to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specificator.

Examples

Input

aaaa


Output

20


Input

abcdef


Output

21


Input

abacabadabacaba


Output

188

Note

In the first sample the function values at x equal to "a", "aa", "aaa" and "aaaa" equal 10, 6, 3 and 1 correspondingly.

In the second sample for any satisfying x the function value is 1.

Solution (in JAVA):

Solution:

import java.util.Arrays;
import java.util.Scanner;


public class SuffixAutomaton {
    long []co;
    long []ans;
    
    static class Node{
        int len,link=-1;
        int a[]=new int[26];
        boolean fin;
        public Node(int le){
            len=le;
        }
    }
    int max;
    Node nodes[];
    int last,sz;
    public SuffixAutomaton(int max){
        this.max=max;
        nodes =new Node[max];
        co=new long[max];
        ans=new long[max];
        
        nodes[0]=new Node(0);
        sz++;
    }
    public void add(char c){
        int ch=c-'a';
        int cur=sz++;
        nodes[cur]=new Node(nodes[last].len+1);
        int p;
        for(p=last;p!=-1 && nodes[p].a[ch]==0;p=nodes[p].link){
            nodes[p].a[ch]=cur;
        }
        if(p==-1)nodes[cur].link=0;
        else{
            int q=nodes[p].a[ch];
            if(nodes[p].len+1==nodes[q].len){
                nodes[cur].link=q;
            }
            else{
                int clone=sz++;
                nodes[clone]=new Node(nodes[p].len+1);
                nodes[clone].a=(int[])nodes[q].a.clone();
                nodes[clone].link=nodes[q].link;
                for(;p!=-1 && nodes[p].a[ch]==q;p=nodes[p].link){
                    nodes[p].a[ch]=clone;
                }
                nodes[q].link=nodes[cur].link=clone;
            }
        }
        last=cur;
    }
    
    public  long count(int n){
        if(co[n]!=0){
            return co[n];
        }
        for(int i=0;i<26;i++){
            if(nodes[n].a[i]!=0){
                co[n]+=count(nodes[n].a[i]);
            }
        }
        if(nodes[n].fin)co[n]++;
        return co[n];
    }
    int it=0;
    public long ans(int n){
        if(ans[n]!=-1)return ans[n];
        ans[n]=0;
        if(nodes[n].link==-1)ans[n]=0;
        else{
            long ac=nodes[n].len-nodes[nodes[n].link].len;
            long reb=co[n];
            ans[n]=ac*((reb*(reb+1))/2);
        }
        
        for(int i=0;i<26;i++){
            ans(nodes[n].a[i]);
        }
        return ans[n];
    }
    public void buildLink(){
        while(last!=0){
            nodes[last].fin=true;
            last=nodes[last].link;
        }
    }
    
    public static void main(String[] args) {
        SuffixAutomaton sa=new SuffixAutomaton(200005);
        Scanner sc=new Scanner (System.in);
        
        String s=sc.next();
        for (char ch:s.toCharArray()){
            sa.add(ch);
        }
        sa.buildLink();
        
        
        Arrays.fill(sa.ans, -1l);
        sa.count(0);
        sa.ans(0);
        long ans=0;
        for(int i=0;i<sa.ans.length;i++){
            if(sa.ans[i]==-1)sa.ans[i]=0;
        }
        for(int i=0;i<sa.ans.length;i++){
            ans+=sa.ans[i];
        }
        
        System.out.println(ans);
        

    }
    
    
}