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>
using namespace std;
char s[(int)(1e5 + 3)];
int n, si[20][(int)(1e5 + 3)], ste = 1, ln = 1, ar[(int)(1e5 + 3)],
                               tut[(int)(1e5 + 3)];
pair<pair<int, int>, int> t[(int)(1e5 + 3)];
int lcp(int bas, int son) {
  int re = 0;
  for (int i = ste; i >= 0; i--)
    if (si[i][bas] == si[i][son]) re += 1 << i, bas += 1 << i, son += 1 << i;
  return re;
}
void build_suffixar() {
  for (int i = 1; i <= n; i++) {
    si[0][i] = s[i] - 'a' + 1;
  }
  while (ln <= n) {
    for (int i = 1; i <= n; i++) {
      if (i + ln <= n)
        t[i] = make_pair(make_pair(si[ste - 1][i], si[ste - 1][i + ln]), i);
      else
        t[i] = make_pair(make_pair(si[ste - 1][i], -1), i);
    }
    sort(t + 1, t + n + 1);
    int co = 1;
    for (int i = 1; i <= n; i++) {
      si[ste][t[i].second] = co;
      if (i < n && (t[i].first.first != t[i + 1].first.first ||
                    t[i].first.second != t[i + 1].first.second))
        co++;
    }
    ste++;
    ln = ln * 2;
  }
  ste--;
  ln /= 2;
  for (int i = 1; i <= n; i++) tut[si[ste][i]] = i;
}
long long int histogram() {
  stack<pair<int, int> > S;
  long long int sum = 0;
  int mx = 0;
  for (int i = 1; i <= n; i++) {
    int index = i;
    while (!S.empty() && S.top().first >= ar[i]) {
      mx = ar[i];
      pair<int, int> temp = S.top();
      S.pop();
      if (!S.empty()) mx = max(mx, S.top().first);
      sum += 1ll * (temp.first - mx) * (i - temp.second) *
             (i - temp.second + 1) / 2;
      index = temp.second;
    }
    S.push(make_pair(ar[i], index));
  }
  return sum;
}
int main() {
  scanf("%s", s + 1);
  n = strlen(s + 1);
  build_suffixar();
  for (int i = 1; i < n; i++) {
    ar[i] = lcp(tut[i], tut[i + 1]);
  }
  printf("%lld\n", histogram() + 1ll * n * (n + 1) / 2);
}