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:
//Created by Aminul on 9/3/2019.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Stack;

import static java.lang.Math.max;

public class CF123D_2 {
    public static void main(String[] args) throws Exception {
        //Scanner in = new Scanner(System.in);
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(System.out);
        char[] s = br.readLine().toCharArray();
        int n = s.length;
        int sa[] = suffixArray(s);
        final int lcp[] = lcp(sa, s);
        long ans = 0;
        SegTree segTree = new SegTree(n + 1);
        for (int i = n - 1; i >= 0; i--) {
            int len = n - sa[i];
            ans += segTree.query(1, len) + len;
            segTree.clearRange(lcp[i] + 1, n);
            segTree.update(1, lcp[i], 1);
        }
        pw.println(ans);
        pw.close();
    }

    static int brute(int n, int sa[], int lcp[]) {
        int ans = 0;
        for (int i = 0; i < n; i++) {
            int len = n - sa[i];
            for (int j = 1; j <= len; j++) {
                ans++;
                for (int k = i + 1; k < n; k++) {
                    if (lcp[k] < j) break;
                    ans++;
                }
            }
        }
        return ans;
    }

    static int[] suffixArray(char[] S) {
        int n = S.length;
        Integer ord[] = new Integer[n];
        for (int i = 0; i < n; i++) ord[i] = n - 1 - i;
        Arrays.sort(ord, (a, b) -> Character.compare(S[a], S[b]));
        int order[] = new int[n];
        for (int i = 0; i < n; i++) order[i] = ord[i];
        //Arrays.sort(order, new Comparator<Integer>() {public int compare(Integer o1, Integer o2) { return S[o1] - S[o2]; }});
        int[] sa = new int[n];
        int[] classes = new int[n];
        for (int i = 0; i < n; i++) {
            sa[i] = order[i];
            classes[i] = S[i];
        }
        for (int len = 1; len < n; len <<= 1) {
            int[] c = classes.clone();
            for (int i = 0; i < n; i++) {
                classes[sa[i]] = i > 0 && c[sa[i - 1]] == c[sa[i]] && sa[i - 1] + len < n
                        && c[sa[i - 1] + (len >> 1)] == c[sa[i] + (len >> 1)] ? classes[sa[i - 1]] : i;
            }
            int[] cnt = new int[n];
            for (int i = 0; i < n; i++) {
                cnt[i] = i;
            }
            int[] s = sa.clone();
            for (int i = 0; i < n; i++) {
                int s1 = s[i] - len;
                if (s1 >= 0) {
                    sa[cnt[classes[s1]]++] = s1;
                }
            }
        }
        return sa;
    }

    static int[] lcp(int[] sa, char[] s) {
        int n = sa.length;
        int[] rank = new int[n];
        for (int i = 0; i < n; i++)
            rank[sa[i]] = i;
        int[] lcp = new int[n];

        for (int i = 0, h = 0; i < n; i++) {
            if (rank[i] < n - 1) {
                for (int j = sa[rank[i] + 1]; max(i, j) + h < s.length
                        && s[i + h] == s[j + h]; ++h)
                    ;
                lcp[rank[i] + 1] = h;
                if (h > 0)
                    --h;
            }
        }
        return lcp;
    }

    static void debug(Object... obj) {
        System.err.println(Arrays.deepToString(obj));
    }

    static class SegTree {
        Node root;
        int n;

        SegTree(int N) {
            n = N;
            root = new Node();
        }

        void pushDown(Node node, int s, int m, int e) {
            if (node.lazy == 0) return;
            if (node.left != null) {
                node.left.value += (m - s + 1) * node.lazy;
                node.left.lazy += node.lazy;
            }
            if (node.right != null) {
                node.right.value += (e - m) * node.lazy;
                node.right.lazy += node.lazy;
            }
            node.lazy = 0;
        }

        void update(int l, int r, int v) {
            update(root, 1, n, l, r, v);
        }

        void update(Node node, int s, int e, int a, int b, int value) {
            if (s > e || s > b || e < a) return;
            if (s >= a && e <= b) {
                node.lazy += value;
                node.value += (e - s + 1) * value;
                return;
            }
            int m = (s + e) / 2;
            if (node.left == null) node.left = new Node();
            if (node.right == null) node.right = new Node();
            pushDown(node, s, m, e);
            update(node.left, s, m, a, b, value);
            update(node.right, m + 1, e, a, b, value);
            node.value = node.left.value + node.right.value;
        }

        void clearRange(int l, int r) {
            root = clearRange(root, 1, n, l, r);
        }

        Node clearRange(Node node, int s, int e, int a, int b) {
            if (s > e || s > b || e < a) return node;
            if (s >= a && e <= b) {
                return new Node();
            }
            int m = (s + e) / 2;
            if (node.left == null) node.left = new Node();
            if (node.right == null) node.right = new Node();
            pushDown(node, s, m, e);
            node.left = clearRange(node.left, s, m, a, b);
            node.right = clearRange(node.right, m + 1, e, a, b);
            node.value = node.left.value + node.right.value;
            return node;
        }

        long query(int l, int r) {
            return query(root, 1, n, l, r);
        }

        long query(Node node, int s, int e, int a, int b) {
            if (s > e || s > b || e < a) return 0;
            if (s >= a && e <= b) {
                return node.value;
            }
            int m = (s + e) / 2;
            if (node.left == null) node.left = new Node();
            if (node.right == null) node.right = new Node();
            pushDown(node, s, m, e);
            return query(node.left, s, m, a, b) + query(node.right, m + 1, e, a, b);
        }

        static class Node {
            Node left, right;
            long value, lazy;

            Node() {
            }

            Node(int v) {
                value = v;
            }

            @Override
            public String toString() {
                return "[" + value + ", " + lazy + "]";
            }
        }
    }
}