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;
const int N = 100010;
int len, n;
char ch[N];
namespace lzr {
void induced_sort(const int n, const int m, const int *S, int *SA,
                  const bool *type, const int *buc, int *lbuc, int *sbuc) {
  int now;
  for (int i = 1; i <= m; i++) sbuc[i] = buc[i] - 1;
  for (int i = 0; i <= n; i++)
    if (SA[i] > 0 && !type[now = SA[i] - 1]) SA[lbuc[S[now]]++] = now;
  for (int i = n; i >= 0; i--)
    if (SA[i] > 0 && type[now = SA[i] - 1]) SA[sbuc[S[now]]--] = now;
}
void SAIS(int n, const int m, const int *const S, int *SA) {
  n--;
  bool type[n + 1];
  int buc[m + 1], lbuc[m + 1], sbuc[m + 1], lms[n + 1], lab[n + 1];
  memset(buc, 0, sizeof(buc));
  memset(lbuc, 0, sizeof(lbuc));
  memset(sbuc, 0, sizeof(sbuc));
  for (int i = n; i >= 0; i--) {
    type[i] = i == n || (S[i] < S[i + 1]) || (S[i] == S[i + 1] && type[i + 1]);
    buc[S[i]]++;
  }
  lbuc[0] = sbuc[0] = 0;
  for (int i = 1; i <= m; i++)
    buc[i] += buc[i - 1], lbuc[i] = buc[i - 1], sbuc[i] = buc[i] - 1;
  int cnt = 0;
  for (int i = 1; i <= n; i++) (type[i] && !type[i - 1]) ? lms[cnt++] = i : 0;
  memset(SA, -1, (n + 1) << 2);
  for (int i = 0; i != cnt; i++) SA[sbuc[S[lms[i]]]--] = lms[i];
  induced_sort(n, m, S, SA, type, buc, lbuc, sbuc);
  int *len = new int[n + 1];
  lms[cnt] = n + 1;
  for (int i = 0; i != cnt; i++) len[lms[i]] = lms[i + 1] - lms[i] + 1;
  int m0 = 0;
  memset(lab, -1, (n + 1) << 2);
  for (int i = 1, p = -1, q = -1; i <= n; i++)
    if ((q = SA[i]) > 0 && type[q] && !type[q - 1]) {
      if (p == -1 || len[p] != len[q] || memcmp(S + p, S + q, len[p] << 2))
        m0++;
      lab[q] = m0;
      p = q;
    }
  lab[n] = 0;
  int *S1 = new int[cnt];
  int *SA1 = new int[cnt + 1];
  for (int i = 0, pos = 0; i <= n; i++) (lab[i] >= 0) ? S1[pos++] = lab[i] : 0;
  if (m0 + 1 == cnt)
    for (int i = 0; i != cnt; i++) SA1[S1[i]] = i;
  else
    SAIS(cnt, m0, S1, SA1);
  lbuc[0] = sbuc[0] = 0;
  for (int i = 1; i <= m; i++) lbuc[i] = buc[i - 1], sbuc[i] = buc[i] - 1;
  memset(SA, -1, (n + 1) << 2);
  for (int i = cnt; i--;) SA[sbuc[S[lms[SA1[i]]]]--] = lms[SA1[i]];
  induced_sort(n, m, S, SA, type, buc, lbuc, sbuc);
}
};  // namespace lzr
using namespace lzr;
inline long long f(int x) { return (long long)x * (x + 1) / 2; }
int sa[N], a[N], rk[N], lcp[N];
int main() {
  scanf("%s", ch);
  n = strlen(ch);
  a[n] = 0;
  for (int(i) = (0); (i) <= (n - 1); (i)++) a[i] = ch[i] - 'a' + 1;
  SAIS(n + 1, 256, a, sa);
  for (int i = 0; i <= n; i++) rk[sa[i]] = i;
  int k = 0, x, y;
  for (int i = 0; i < n; i++) {
    if (k != 0)
      k--;
    else
      k = 0;
    x = sa[rk[i]];
    y = sa[rk[i] - 1];
    while (ch[x + k] == ch[y + k]) k++;
    lcp[rk[i]] = k;
  }
  int h = 0;
  long long ans = 0;
  vector<pair<pair<int, int>, int> > v;
  lcp[n + 1] = 0;
  sa[n + 1] = n;
  for (int(i) = (1); (i) <= (n + 1); (i)++) {
    while (!v.empty() && v.back().first.second > lcp[i]) {
      pair<pair<int, int>, int> &now = v.back();
      if (now.first.first < lcp[i]) {
        ans += (now.first.second - lcp[i]) * f(i - now.second);
        now.first.second = lcp[i];
      } else
        ans += (now.first.second - now.first.first) * f(i - now.second),
            v.pop_back();
    }
    v.push_back(make_pair(make_pair(lcp[i], n - sa[i]), i));
  }
  printf("%I64d", ans);
  return 0;
}