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 rk[N], len, n;
char ch[N], v[N];
int a[N];
namespace lzr {
int sa[N], lcp[N];
struct cmp {
  const int h, *g;
  cmp(int h, int *g) : h(h), g(g) {}
  bool operator()(int l, int r) {
    return g[l] != g[r] ? g[l] < g[r] : g[l + h] < g[r + h];
  }
};
void build(const char *t, int n) {
  static int g[N], rk[N];
  for (int(i) = (0); (i) <= (n); (i)++) sa[i] = i, g[i] = t[i];
  rk[0] = rk[n] = 0;
  sort(sa, sa + n + 1, cmp(0, g));
  for (int h = 1; rk[n] != n; h *= 2) {
    cmp a(h, g);
    sort(sa, sa + n + 1, a);
    for (int(i) = (0); (i) <= (n - 1); (i)++)
      rk[i + 1] = rk[i] + a(sa[i], sa[i + 1]);
    for (int(i) = (0); (i) <= (n); (i)++) g[sa[i]] = rk[i];
  }
  for (int(i) = (0); (i) <= (n); (i)++) rk[sa[i]] = i;
  int h = 0;
  for (int(i) = (0); (i) <= (n - 1); (i)++) {
    const int j = sa[rk[i] - 1];
    while (j + h < n && i + h < n && t[j + h] == t[i + h]) h++;
    lcp[rk[i]] = h;
    if (h) h--;
  }
  lcp[0] = -1;
}
};  // namespace lzr
using namespace lzr;
inline long long f(int x) { return (long long)x * (x + 1) / 2; }
int main() {
  scanf("%s", ch);
  n = strlen(ch);
  build(ch, n);
  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;
}