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>
char s[100005];
int sa[100005], s_rank[100005], lcp[100005], x1[100005], x2[100005], c[100005];
int stack[100005];
static inline int Max(int x, int y) { return x > y ? x : y; }
void sa_init(int n) {
  int m = 256;
  int *x = x1, *y = x2;
  for (int j = 0; j < m; ++j) {
    c[j] = 0;
  }
  for (int i = 0; i < n; ++i) {
    c[x[i] = (unsigned char)s[i]]++;
  }
  for (int j = 1; j < m; ++j) {
    c[j] += c[j - 1];
  }
  for (int i = n - 1; i >= 0; --i) {
    sa[c[x[i]]--] = i;
  }
  for (int h = 1; h < n; h <<= 1) {
    int k = 0;
    for (int i = n - h; i < n; ++i) {
      y[k++] = i;
    }
    for (int i = 1; i <= n; ++i) {
      if (sa[i] >= h) {
        y[k++] = sa[i] - h;
      }
    }
    for (int j = 0; j < m; ++j) {
      c[j] = 0;
    }
    for (int i = 0; i < n; ++i) {
      c[x[y[i]]]++;
    }
    for (int j = 1; j < m; ++j) {
      c[j] += c[j - 1];
    }
    for (int i = n - 1; i >= 0; --i) {
      sa[c[x[y[i]]]--] = y[i];
    }
    int *t = x;
    x = y;
    y = t;
    m = 1;
    x[sa[1]] = 0;
    for (int i = 2; i <= n; ++i) {
      if (y[sa[i]] == y[sa[i - 1]] && sa[i] + h < n && sa[i - 1] + h < n &&
          y[sa[i] + h] == y[sa[i - 1] + h]) {
        x[sa[i]] = m - 1;
      } else {
        x[sa[i]] = m++;
      }
    }
  }
  sa[0] = n;
  for (int i = 0; i <= n; ++i) {
    s_rank[sa[i]] = i;
  }
  int h = 0;
  for (int i = 0; i < n; ++i) {
    int j = sa[s_rank[i] - 1];
    if (h > 0) {
      --h;
    }
    for (; i + h < n && j + h < n; ++h) {
      if (s[i + h] != s[j + h]) {
        break;
      }
    }
    lcp[s_rank[i] - 1] = h;
  }
}
int main(void) {
  while (scanf("%s", s) != EOF) {
    int n = (int)strlen(s);
    sa_init(n);
    long long ans = 0;
    int top = 0;
    for (int i = 0; i < n; ++i) {
      while (top > 0 && lcp[stack[top - 1]] >= lcp[i]) {
        int j = stack[--top];
        ans += (n - sa[j + 1]) - Max(lcp[j], lcp[j + 1]);
        if (top > 0) {
          int l = stack[top - 1];
          long long m = i - l;
          ans += m * (m + 1) / 2 * (lcp[j] - Max(lcp[l], lcp[i]));
        }
      }
      stack[top++] = i;
    }
    while (top > 0) {
      int j = stack[--top];
      if (j + 1 == n) {
        ans += (n - sa[j + 1]) - lcp[j];
      } else {
        ans += (n - sa[j + 1]) - Max(lcp[j], lcp[j + 1]);
      }
      if (top > 0) {
        int l = stack[top - 1];
        long long m = n - l;
        ans += m * (m + 1) / 2 * (lcp[j] - lcp[l]);
      }
    }
    printf("%lld\n", ans);
  }
  return 0;
}