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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

/**
 * @author Pavel Mavrin
 */
public class Z123D {

    private String ss;
    private SuffixAutomaton aut;

    private void solve() throws IOException {
        ss = next();
        ss += (char)('z' + 1);
        aut = new SuffixAutomaton(ss);
//        for (int i= 1; i < aut.n; i++) {
//            for (int j = 0; j < aut.ALPHA_SIZE; j++) {
//                int x = aut.next[i * aut.ALPHA_SIZE + j];
//                if (x != 0) {
//                    System.out.println(i + " - " + x + " " + (char)('a'+j));
//                }
//            }
//        }
        size = new int[aut.n];
        p = new int[aut.n];
        cur = aut.n - 1;
        z = new boolean[aut.n];
        dfs(aut.root);
        size2 = new int[aut.n];
        size2[aut.root] = 1;
        for (int vv = 0; vv < aut.n; vv++) {
            int v = p[vv];
            for (int i = 0; i < SuffixAutomaton.ALPHA_SIZE; i++) {
                int x = v * SuffixAutomaton.ALPHA_SIZE + i;
                int u = aut.next[x];
                if (u > 0) {
                    size2[u] += size2[v];
                    res += 1l * size2[v] * size[u] * (size[u] + 1) / 2;
                }
            }
        }
//        System.out.println(Arrays.toString(p));
//        System.out.println(Arrays.toString(size));
//        System.out.println(Arrays.toString(size2));
        out.println(res - ss.length());
    }

    int[] size;
    int[] size2;
    int[] p;
    int cur;
    boolean[] z;

    long res = 0;

    private void dfs(int v) {
        if (z[v]) return;
        z[v] = true;
        if (v == aut.last) {
            size[v] = 1;
        } else {
            for (int i = 0; i < SuffixAutomaton.ALPHA_SIZE; i++) {
                int x = v * SuffixAutomaton.ALPHA_SIZE + i;
                int u = aut.next[x];
                if (u > 0) {
                    dfs(u);
                    size[v] += size[u];
                }
            }
        }
        p[cur--] = v;
    }


    /**
     * Author: Sergey Kopeliovich (Burunduk30@gmail.com)
     * (translated from C++ by Pavel Mavrin)
     */

    class SuffixAutomaton {

        public static final int ALPHA_SIZE = 27;
        public int root, last, n;
        public final int len[], suf[], next[];

        public SuffixAutomaton(String s) {
            len = new int[2 * s.length() + 2];
            suf = new int[2 * s.length() + 2];
            //compressed 2d array. next[i][j] -> next[i * ALPHA_SIZE + j];
            next = new int[(2 * s.length() + 2) * ALPHA_SIZE];
            for (int i = 0; i < ALPHA_SIZE; i++)
                next[i] = 1;
            n = 1;
            root = last = newV(0, 0);
            for (int i = 0; i < s.length(); i++) {
                int ch = s.charAt(i) - 'a';
                int R, Q, P = last;
                last = newV(len[last] + 1, 0);
                while (next[P * ALPHA_SIZE + ch] == 0) {
                    next[P * ALPHA_SIZE + ch] = last;
                    P = suf[P];
                }
                if (P == 0)
                    suf[last] = 1;
                else if (len[Q = next[P * ALPHA_SIZE + ch]] == len[P] + 1)
                    suf[last] = Q;
                else {
                    R = newV(len[P] + 1, suf[Q]);
                    suf[last] = suf[Q] = R;
                    System.arraycopy(next, Q * ALPHA_SIZE, next, R * ALPHA_SIZE, ALPHA_SIZE);
                    while (P > 0 && next[P * ALPHA_SIZE + ch] == Q) {
                        next[P * ALPHA_SIZE + ch] = R;
                        P = suf[P];
                    }
                }
            }
        }

        private int newV(int l, int _suf) {
            if ((n >= len.length)) throw new AssertionError();
            for (int i = 0; i < ALPHA_SIZE; i++) {
                next[n * ALPHA_SIZE + i] = 0;
            }
            len[n] = l;
            suf[n] = _suf;
            return n++;
        }
    }


    //eqkrqe
    // e 3 6+5+4+3+2+1 21

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st;
    PrintWriter out = new PrintWriter(System.out);

    String next() throws IOException {
        while (st == null || !st.hasMoreTokens()) {
            st = new StringTokenizer(br.readLine());
        }
        return st.nextToken();
    }

    int nextInt() throws IOException {
        return Integer.parseInt(next());
    }

    public static void main(String[] args) throws IOException {
        new Z123D().run();
    }

    private void run() throws IOException {
        solve();
        out.close();
    }

}