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;

public class AString implements Runnable {
    static final int INF = 1000000;

    static class IntervalTree {
        int[] subtreeMin;
        int n;

        public IntervalTree(int n) {
            this.n = n;
            subtreeMin = new int[4 * n + 10];
            Arrays.fill(subtreeMin, INF);
        }

        void update(int at, int by) {
            internalUpdate(0, 0, n - 1, at, by);
        }

        private void internalUpdate(int root, int rl, int rr, int at, int by) {
            if (rl == rr)
                subtreeMin[root] = by;
            else {
                int rm = (rl + rr) / 2;
                if (at <= rm)
                    internalUpdate(root * 2 + 1, rl, rm, at, by);
                else
                    internalUpdate(root * 2 + 2, rm + 1, rr, at, by);
                subtreeMin[root] = Math.min(subtreeMin[root * 2 + 1], subtreeMin[root * 2 + 2]);
            }
        }

        int get(int l, int r) {
            return internalGet(0, 0, n - 1, l, r);
        }

        private int internalGet(int root, int rl, int rr, int l, int r) {
            l = Math.max(l, rl);
            r = Math.min(r, rr);
            if (l > r) return INF;
            if (l == rl && r == rr)
                return subtreeMin[root];
            int rm = (rl + rr) / 2;
            return Math.min(internalGet(root * 2 + 1, rl, rm, l, r), internalGet(root * 2 + 2, rm + 1, rr, l, r));
        }
    }

    private void solve() throws IOException {
        String s = nextToken() + (char) ('a' - 1);
        int[] id = new int[s.length()];
        int[] cnt = new int[Math.max(27, s.length())];
        int[] perm = new int[s.length()];
        IntervalTree eqLen = new IntervalTree(s.length() - 1);
        for (int i = 0; i < s.length(); ++i) {
            id[i] = s.charAt(i) - 'a' + 1;
            ++cnt[id[i]];
        }
        int[] ptr = new int[cnt.length];
        ptr[0] = 0;
        for (int i = 0; i + 1 < cnt.length; ++i)
            ptr[i + 1] = ptr[i] + cnt[i];
        for (int i = 0; i < s.length(); ++i) {
            perm[ptr[id[i]]++] = i;
        }
        for (int i = 0; i + 1 < s.length(); ++i)
            if (id[perm[i]] != id[perm[i + 1]])
                eqLen.update(i, 0);
        int len = 1;
        int[] nperm = new int[s.length()];
        int[] nid = new int[s.length()];
        while (len < s.length()) {
            Arrays.fill(cnt, 0);
            for (int x : id) ++cnt[x];
            ptr[0] = 0;
            for (int i = 0; i + 1 < cnt.length; ++i)
                ptr[i + 1] = ptr[i] + cnt[i];
            for (int second = 0; second < s.length(); ++second) {
                int first = (perm[second] - len + s.length()) % s.length();
                nperm[ptr[id[first]]++] = first;
            }
            int lastId = 0;
            for (int i = 0; i < s.length(); ++i) {
                if (i != 0) {
                    int p1 = nperm[i];
                    int p2 = nperm[i - 1];
                    if (id[p1] != id[p2]) {
                        ++lastId;
                    } else {
                        int n1 = (p1 + len) % s.length();
                        int n2 = (p2 + len) % s.length();
                        if (id[n1] != id[n2]) {
                            int pos1 = ptr[id[n1]] - 1;
                            int pos2 = ptr[id[n2]] - 1;
                            eqLen.update(i - 1, len + eqLen.get(Math.min(pos1, pos2), Math.max(pos1, pos2) - 1));
                            ++lastId;
                        }
                    }
                }
                nid[nperm[i]] = lastId;
            }
            {
                int[] tmp = perm;
                perm = nperm;
                nperm = tmp;
                tmp = id;
                id = nid;
                nid = tmp;
            }
            len *= 2;
        }
        int[] stackCnt = new int[s.length()];
        int[] stackLen = new int[s.length()];
        int stackPos = 0;
        int stackTotalLen = 0;
        long res = 0;
        for (int i = 1; i < s.length(); ++i) {
            int cur = perm[i];
            int commonLen = eqLen.get(i - 1, i - 1);
            //System.out.println(cur + " " + commonLen);
            int curLen = s.length() - cur - 1;
            while (stackTotalLen > commonLen) {
                int by = Math.min(stackLen[stackPos - 1], stackTotalLen - commonLen);
                int byCnt = stackCnt[stackPos - 1] + i;
                res += (long) byCnt * (byCnt + 1) / 2 * by;
                stackLen[stackPos - 1] -= by;
                if (stackLen[stackPos - 1] == 0) --stackPos;
                stackTotalLen -= by;
            }
            if (stackTotalLen != commonLen) throw new RuntimeException();
            if (curLen > commonLen) {
                stackCnt[stackPos] = -i;
                stackLen[stackPos] = curLen - commonLen;
                ++stackPos;
                stackTotalLen += curLen - commonLen;
            }
        }
        while (stackTotalLen > 0) {
            int by = stackLen[stackPos - 1];
            int byCnt = stackCnt[stackPos - 1] + s.length();
            res += (long) byCnt * (byCnt + 1) / 2 * by;
            stackLen[stackPos - 1] -= by;
            if (stackLen[stackPos - 1] == 0) --stackPos;
            stackTotalLen -= by;
        }
        writer.println(res);
    }

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

    BufferedReader reader;
    StringTokenizer tokenizer;
    PrintWriter writer;

    public void run() {
        try {
            reader = new BufferedReader(new InputStreamReader(System.in));
            tokenizer = null;
            writer = new PrintWriter(System.out);
            solve();
            reader.close();
            writer.close();
        } catch (Exception e) {
            e.printStackTrace();
            System.exit(1);
        }
    }

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

    long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }

    double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }

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