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[200010];
int n, k;
int sa[200010];
int ra[200010], tr[200010];
int lcp[200010];
int l[200010], r[200010];
stack<int> ls, rs;
set<long long> ss;
bool CmpSa(int a, int b) {
  if (ra[a] != ra[b]) return ra[a] < ra[b];
  int aa = a + k < n ? ra[a + k] : -1;
  int bb = b + k < n ? ra[b + k] : -1;
  return aa < bb;
}
void GaoSa() {
  for (int i = 0; i <= n; ++i) {
    sa[i] = i;
    ra[i] = i < n ? s[i] : -1;
  }
  for (k = 1; k <= n; k <<= 1) {
    sort(sa, sa + n + 1, CmpSa);
    tr[sa[0]] = 0;
    for (int i = 1; i <= n; ++i) {
      tr[sa[i]] = tr[sa[i - 1]] + CmpSa(sa[i - 1], sa[i]);
    }
    memcpy(ra, tr, sizeof(int) * (n + 1));
  }
}
void GaoLcp() {
  int tmp = 0;
  for (int i = 0; i < n; ++i) {
    int rk = ra[i];
    int j = sa[rk - 1];
    if (tmp > 0) --tmp;
    while (i + tmp < n && j + tmp < n && s[i + tmp] == s[j + tmp]) {
      ++tmp;
    }
    lcp[rk - 1] = tmp;
  }
}
inline long long Hash(int b, int c) { return b * 1000000ll + c; }
int main() {
  scanf("%s", s);
  n = strlen(s);
  s[n] = '|';
  memcpy(s + n + 1, s, sizeof(char) * n);
  n = 2 * n + 1;
  GaoSa();
  GaoLcp();
  for (int i = 0; i <= n; ++i) {
    while (!rs.empty() && lcp[rs.top()] > lcp[i]) {
      r[rs.top()] = i;
      rs.pop();
    }
    rs.push(i);
  }
  for (int i = n; i >= 0; --i) {
    while (!ls.empty() && lcp[ls.top()] > lcp[i]) {
      l[ls.top()] = i;
      ls.pop();
    }
    ls.push(i);
  }
  long long ans = 0;
  for (int i = 1; i < n - 1; ++i) {
    if (lcp[i]) {
      if (ss.find(Hash(lcp[i], l[i])) != ss.end()) continue;
      long long tmp = (r[i] - l[i]) / 2;
      tmp = tmp * (tmp + 1) / 2;
      ans += tmp * (lcp[i] - max(lcp[l[i]], lcp[r[i]]));
      ss.insert(Hash(lcp[i], l[i]));
    }
  }
  cout << ans << endl;
  return 0;
}