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.StringTokenizer;

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

    private SuffixTree tree;
    private int k;
    private String ss;

    private void solve() throws IOException {
        ss = next();
        int[] s = new int[ss.length() + 1];
        for (int i = 0; i < ss.length(); i++) {
            s[i] = ss.charAt(i) - 'a' + 1;
        }
        tree = new SuffixTree(s);

//        print(tree.root, 0);
        size = new int[tree.vn];
        dfs(tree.root);
        res -= ss.length() + 1;
        out.println(res);
    }

    int[] size;

//    private void print(int v, int indent) {
//        String s = "";
//        for (int i = 0; i < indent; i++) {
//            s += " ";
//        }
//        for (int i = 0; i < SuffixTree.ALPHA_SIZE; i++) {
//            int u = tree.edge_next[v * SuffixTree.ALPHA_SIZE + i];
//            if (u > 0) {
//                System.out.println(s + ss.substring(
//                        tree.edge_st[v * SuffixTree.ALPHA_SIZE + i],
//                        tree.edge_st[v * SuffixTree.ALPHA_SIZE + i] + tree.edge_len[v * SuffixTree.ALPHA_SIZE + i]
//                ));
//                print(tree.edge_next[v * SuffixTree.ALPHA_SIZE + i], indent + 1);
//            }
//        }
//    }

    long res = 0;

    private void dfs(int v) {
        int dd = 0;
        for (int i = 0; i < SuffixTree.ALPHA_SIZE; i++) {
            int x = v * SuffixTree.ALPHA_SIZE + i;
            int len = tree.edge_len[x];
            int u = tree.edge_next[x];
            if (u > 0) {
                dfs(u);
                res += 1l * len * size[u] * (size[u] + 1) / 2;
                size[v] += size[u];
                dd++;
            }
        }
        if (dd == 0) {
            size[v] = 1;
        }
    }

    class SuffixTree {

        private static final int ALPHA_SIZE = 27;

        int s[], n, vn, root, suf[], dep[], size[];
        int[] edge_st, edge_len, edge_next;

        int newV(int d, int end) {
            assert (vn < suf.length);
            dep[vn] = d;
            size[vn] = end;
            return vn++;
        }

        int split(int v, int c, int i) {
            int a = v * ALPHA_SIZE + c;
            int u = newV(dep[v] + i, 0);
            int b = u * ALPHA_SIZE + s[edge_st[a] + i];
            edge_st[b] = edge_st[a] + i;
            edge_len[b] = edge_len[a] - i;
            edge_next[b] = edge_next[a];
            edge_len[a] = i;
            edge_next[a] = u;
            return u;
        }

        void create(int u, int c, int i) {
            int x = u * ALPHA_SIZE + c;
            edge_st[x] = i;
            edge_len[x] = n - i;
            edge_next[x] = newV(dep[u] + (n - i), 1);
        }

        public SuffixTree(int[] s) {
            this.s = s;
            this.n = s.length;
            int len = 1 + n * 2;
            suf = new int[len];
            dep = new int[len];
            size = new int[len];
            edge_len = new int[len * ALPHA_SIZE];
            edge_next = new int[len * ALPHA_SIZE];
            edge_st = new int[len * ALPHA_SIZE];

            vn = 0;
            root = newV(0, 0);

            int v = 0, cur_c = 0, cur_i = 0;
            for (int i = 0; i < n; i++) {
                if (cur_i > 0 && cur_i == edge_len[v * ALPHA_SIZE + cur_c]) {
                    v = edge_next[v * ALPHA_SIZE + cur_c];
                    cur_i = 0;
                }
                int c = s[i], last = -1;
                int t = edge_st[v * ALPHA_SIZE + cur_c];
                while (cur_i > 0 && s[t + cur_i] != c) {
                    int w = suf[v], u = split(v, cur_c, cur_i);
                    create(u, c, i);
                    if (last != -1)
                        suf[last] = u;
                    last = u;
                    if (v == 0) {
                        t++;
                        cur_i--;
                    }
                    int a;
                    while (cur_i > 0 && edge_len[a = w * ALPHA_SIZE + (cur_c = s[t])] <= cur_i) {
                        cur_i -= edge_len[a];
                        w = edge_next[a];
                        t += edge_len[a];
                    }
                    v = w;
                    if (cur_i == 0)
                        suf[last] = v;
                }
                if (cur_i > 0) {
                    cur_i++;
                } else {
                    cur_i = 1;
                    cur_c = c;
                    while (edge_len[v * ALPHA_SIZE + c] < cur_i) {
                        create(v, c, i);
                        if (v > 0)
                            v = suf[v];
                        else
                            cur_i = 0;
                    }
                }
            }
        }
    }


    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();
    }

}