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.io.*;
import java.util.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;
import java.util.*;
// aoj2292
public class Main {
    public static void main(String[]args){
        new Main().run();
    }

    private void run() {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        long res = solve(s+'$');
        System.out.println(res);
    }

    private long solve(String s) {
        int n = s.length();
        int[] sa = suffixArray_log(s);
        int[] sainv = new int[sa.length];
        for (int i = 0; i < sa.length; i++) {
            sainv[sa[i]] = i;
        }
        int[] lcp = calcLCP(sa, s);
        E[] ordLcp = new E[lcp.length];
        for (int i = 0; i < lcp.length; i++) {
            ordLcp[i] = new E(i, lcp[i]);
        }
//      debug("lcp",lcp);
        sort(ordLcp);
        RMQ rmq = new RMQ(lcp.length);
        for (int i = 0; i < lcp.length; i++) {
            rmq.update(i, lcp[i]);
        }
        
        X = 0;
        long res = 0;
        UnionFind uf = new UnionFind(s.length());
        for(int k = n-1,il=0;k>=1;k--){
            X++;
            uf.num[sainv[n-1-k]]++;
            while(il<ordLcp.length && ordLcp[il].k == k){
                uf.union(ordLcp[il].i, ordLcp[il].i+1);
                il++;
            }
            res += X;
//          debug(k,X);
        }
        return res;
    }

    private void debug(Object... os) {
        System.err.println(deepToString(os));
    }

    private long func(long n) {
        return (n+1)*n/2;
    }

    long X;
    
    class UnionFind{
        final int[] tree;
        long[] num;
        
        public UnionFind(int n){
            this.tree=new int[n];
            num=new long[n];
            fill(tree,-1);
        }
        void union(int x,int y){
            x=root(x);
            y=root(y);
            if(x!=y){
                if(tree[x]>tree[y]){
                    int t=x;x=y;y=t;
                }
                // x <- y
                X -= func(num[x]);
                X -= func(num[y]);
                num[x] += num[y];
                X += func(num[x]);
                
                tree[x]+=tree[y];
                tree[y]=x;
            }
        }
        
        boolean find(int x,int y){
            return root(x)==root(y);
        }
        
        int root(int x){
            return tree[x]<0?x:(tree[x]=root(tree[x]));
        }
        
        int size(int x){
            return -tree[root(x)];
        }
    }

    
    class RMQ {
        private int[] dat;
        private int n;
        public RMQ(int _n){
            n=1;
            while(n<_n)n<<=1;
            dat=new int[n+n];
            Arrays.fill(dat,Integer.MAX_VALUE);
        }
        
        public void update(int i,int a) {
            i+=n-1;
            dat[i] = a;
            while(i>0) {
                i=(i-1)>>1;
                dat[i] = Math.min(dat[(i<<1)+1],dat[(i<<1)+2]);
            }
        }
        
        public int query(int l,int r) {
            return query(l,r,0,0,n);
        }

        private int query(int a,int b,int i,int l,int r){
            if(r<=a || b<=l)return Integer.MAX_VALUE;
            if(a<=l && r<=b)return dat[i];
            int vl = query(a,b,(i<<1)+1,l,(l+r)>>>1);
            int vr = query(a,b,(i<<1)+2,(l+r)>>>1,r);
            return Math.min(vl,vr);
        }
    }
    
    class E implements Comparable<E>{
        int i,k;

        public E(int i, int k) {
            super();
            this.i = i;
            this.k = k;
        }
        public int compareTo(E o) {
            return - (k - o.k);
        }
        @Override
        public String toString() {
            return "E [i=" + i + ", k=" + k + "]";
        }
        
    }
    
    public int[] calcLCP(int[] SA,String s) {
        if(SA.length != s.length())throw new IllegalArgumentException();
        int n = s.length();
        int[] rank=new int[n];// s[i..] がSAにおいて何番目か.
        for(int i=0;i<n;i++)rank[SA[i]]=i;
        int[] lcp=new int[n-1];
        for(int i=0,h=0;i<n;i++)if(rank[i]<n-1) {
            while(s.charAt(i+h) == s.charAt(SA[rank[i]+1]+h))h++;
            lcp[rank[i]]=h;
            if(h>0)h--;
        }
        return lcp;
    }
    
    /**
     * s に対するsuffix arrayを返す.
     * s[n-1] は,それ以外のどの文字よりも小さくなければならない.
     * O(n log n).
     * n=800000 で1s くらい.
     * wataさんのライブラリを参考にした.
     */
    public int[] suffixArray_log(String s){
        int n=s.length()-1;
        char[] cs = s.toCharArray();
        int[] is=new int[n+1];
        for (int i = 0; i < n+1; i++) {
            is[i] = cs[i];
        }
        int[] si = indexSort(is);
        int[] a=new int[n+1],b=new int[n+1];
        for(int h=0;;){
            for (int i = 0; i < n; i++) {
                int x=si[i+1],y=si[i];
                b[i+1]=b[i];
                if(is[x]>is[y] || is[x+h]>is[y+h])b[i+1]++;
            }
            for (int i = 0; i < n+1; i++) {
                is[si[i]] = b[i];
            }
            if(b[n]==n)break;
            h = max(1,h<<1);
            for(int k=h;k>=0;k-=h){
                fill(b,0);
                b[0]=k;
                for (int i = k; i < n+1; i++) {
                    b[is[i]]++;
                }
                for (int i = 0; i < n; i++) {
                    b[i+1]+=b[i];
                }
                for(int i=n;i>=0;i--){
                    a[--b[si[i]+k>n?0:is[si[i]+k]]]=si[i];
                }
                int[] tmp=si;si=a;a=tmp;
            }
        }
        return si;
    }
    
    private int[] indexSort(int[] is) {
        int n=is.length;
        long[] ls=new long[n];
        for (int i = 0; i < n; i++) {
            ls[i]=(long)is[i]<<32 | i;
        }
        sort(ls);
        int[]res=new int[n];
        for (int i = 0; i < n; i++) {
            res[i]=(int)ls[i];
        }
        return res;
    }

    private String rev(String s) {
        return new StringBuilder(s).reverse().toString();
    }

    private String sand(String s) {
        StringBuilder b = new StringBuilder();
        for(char c:s.toCharArray()){
            b.append('*');
            b.append(c);
        }
        b.append('*');
        return b.toString();
    }
}