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 CPP):

Solution:
#include <bits/stdc++.h>
struct sNode {
  int l, r;
  int pl, pr;
  int pos;
};
sNode nodes[700000];
int nodesCnt;
int LCP[300005];
int BuildTree(int l, int r) {
  int cur = nodesCnt++;
  nodes[cur].l = l;
  nodes[cur].r = r;
  nodes[cur].pos = l;
  if (l < r) {
    nodes[cur].pl = BuildTree(l, (l + r) / 2);
    nodes[cur].pr = BuildTree((l + r) / 2 + 1, r);
  }
  return cur;
}
void Update(int i, int root) {
  if (nodes[root].l < nodes[root].r) {
    if (i <= nodes[nodes[root].pl].r)
      Update(i, nodes[root].pl);
    else
      Update(i, nodes[root].pr);
    if (LCP[nodes[nodes[root].pl].pos] <= LCP[nodes[nodes[root].pr].pos])
      nodes[root].pos = nodes[nodes[root].pl].pos;
    else
      nodes[root].pos = nodes[nodes[root].pr].pos;
  }
}
int Get(int l, int r, int root) {
  if (l <= nodes[root].l && r >= nodes[root].r) return nodes[root].pos;
  int ans = 100000000;
  int pos = -1;
  if (l <= nodes[nodes[root].pl].r && nodes[nodes[root].pl].l <= r) {
    int tmp = Get(l, r, nodes[root].pl);
    if (tmp != -1 && LCP[tmp] < ans) {
      ans = LCP[tmp];
      pos = tmp;
    }
  }
  if (l <= nodes[nodes[root].pr].r && nodes[nodes[root].pr].l <= r) {
    int tmp = Get(l, r, nodes[root].pr);
    if (tmp != -1 && LCP[tmp] < ans) {
      ans = LCP[tmp];
      pos = tmp;
    }
  }
  return pos;
}
char input[100009];
int n;
int root;
int suffArr[100009];
int newSuffArr[100009];
int bucket[100009];
int nextPos[100009];
int posInSuffArr[100009];
int update[100009];
int cnt[128];
void BuildSuffArr() {
  root = BuildTree(0, n - 1);
  for (int i = 0; i < n; i++) LCP[i] = 100000000;
  for (int i = 0; i < n; i++) cnt[(int)input[i]]++;
  for (int i = 1; i < 128; i++)
    cnt[i] += cnt[i - 1], LCP[cnt[i]] = 0, Update(cnt[i], root);
  for (int i = 0; i < n; i++) suffArr[--cnt[(int)input[i]]] = i;
  LCP[0] = 100000000, Update(0, root);
  newSuffArr[0] = suffArr[0];
  for (int step = 1; step <= n; step *= 2) {
    for (int i = 1; i < n; i++) {
      posInSuffArr[suffArr[i]] = i;
      if (LCP[i] != 100000000)
        bucket[i] = i, nextPos[i] = i;
      else
        bucket[i] = bucket[i - 1];
    }
    for (int i = 0; i < n; i++) {
      if (suffArr[i] >= step)
        newSuffArr[nextPos[bucket[posInSuffArr[suffArr[i] - step]]]++] =
            suffArr[i] - step;
    }
    for (int i = 1; i < n; i++) {
      if (LCP[i] == 100000000 &&
          bucket[posInSuffArr[newSuffArr[i] + step]] !=
              bucket[posInSuffArr[newSuffArr[i - 1] + step]]) {
        int a = bucket[posInSuffArr[newSuffArr[i] + step]];
        int b = bucket[posInSuffArr[newSuffArr[i - 1] + step]];
        if (a > b) {
          int tmp = a;
          a = b;
          b = tmp;
        }
        update[i] = step + LCP[Get(a + 1, b, root)];
      }
    }
    for (int i = 0; i < n; i++) {
      if (update[i]) LCP[i] = update[i], update[i] = 0, Update(i, root);
      suffArr[i] = newSuffArr[i];
    }
  }
}
long long ans;
void Solve(int l, int r, int k) {
  if (l == r) {
    int tt = n - suffArr[l] - 1;
    ans += (long long)(tt - k);
    return;
  }
  int t = Get(l + 1, r, root);
  long long cnt = (long long)(LCP[t] - k) * (long long)(r - l + 1) *
                  (long long)(r - l + 2) / 2;
  ans += cnt;
  Solve(l, t - 1, LCP[t]);
  Solve(t, r, LCP[t]);
}
int main() {
  scanf("%s", input);
  n = strlen(input);
  input[n++] = 'a' - 1;
  BuildSuffArr();
  Solve(1, n - 1, 0);
  printf("%I64d", ans);
}