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

import java.math.BigInteger;
import java.util.*;
import java.io.*;

public class Main
{
    void main() throws Exception
    {
        Scanner sc = new Scanner(System.in) ;
        PrintWriter out = new PrintWriter(System.out) ;
        char [] a = sc.next().toCharArray() ;
        SuffixAutomaton sa = new SuffixAutomaton(a) ;
        long ans = 0 ;
        for(int i = 1 ; i <= sa.idx ; i++)
            ans += ((1L * sa.cnt[i] * (sa.cnt[i] + 1)) / 2) * (sa.len[i] - sa.len[sa.link[i]]) ;
        out.println(ans);
        out.flush();
        out.close();
    }
    class SuffixAutomaton
    {
        int[] link, len , cnt;
        int [][] next ;
        int lst, idx;

        SuffixAutomaton(char[] s)
        {
            int n = s.length;
            link = new int[n<<1];
            len = new int[n<<1];
            next = new int [26][n << 1] ;
            cnt = new int [n << 1] ;
            for(char c: s)
                addLetter(c - 'a');

            Integer [] id = new Integer[idx + 1] ;
            for(int i = 0 ; i <= idx ; i++)
                id[i] = i ;
            sort(id , (x , y)->len[y] - len[x]);

            for(int v : id)
                cnt[link[v]] += cnt[v] ;
        }

        void addLetter(int c)
        {
            int cur = ++idx, p = lst;
            while(next[c][p] == 0) { next[c][p] = cur; p = link[p]; }
            cnt[cur] = 1 ;
            int q = next[c][p];
            if(q != cur)
                if(len[q] == len[p] + 1)
                    link[cur] = q;
                else
                {
                    int clone = ++idx;
                    len[clone] = len[p] + 1;
                    link[clone] = link[q];
                    for(int i = 0 ; i < 26 ; i++)
                        next[i][clone] = next[i][q] ;
                    link[cur] = link[q] = clone;
                    while(next[c][p] == q) { next[c][p] =  clone; p = link[p]; }
                }
            len[cur] = len[lst] + 1;
            lst = cur;
        }
    }

    class Scanner
    {
        BufferedReader br;
        StringTokenizer st;

        Scanner(InputStream in)
        {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        Scanner(String path) throws Exception
        {
            br = new BufferedReader(new FileReader(path)) ;
        }
        String next() throws Exception
        {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }
        int nextInt() throws Exception { return Integer.parseInt(next()); }

        long nextLong() throws Exception { return Long.parseLong(next()); }

        double nextDouble() throws Exception { return Double.parseDouble(next());}
    }

    public static void main (String [] args) throws Exception {(new Main()).main();}

}