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 long long MAXN = 1e5 + 10;
const long long MAX_LOG = 20;
string s;
stack<pair<long long, long long> > stk;
long long rnk[MAXN][MAX_LOG];
pair<pair<long long, long long>, long long> w[MAXN];
long long a[MAXN];
long long sa[MAXN];
long long sz;
long long lcp(long long x, long long y) {
  if (x > y) {
    swap(x, y);
  }
  long long res = 0;
  for (long long i = MAX_LOG - 1; i >= 0; i--) {
    if (y + (1 << i) <= sz && rnk[x][i] == rnk[y][i]) {
      x += (1 << i);
      y += (1 << i);
      res += (1 << i);
    }
  }
  return res;
}
int main() {
  ios_base ::sync_with_stdio(false);
  cin.tie(0);
  cin >> s;
  sz = (long long)(s.size());
  for (long long i = 0; i < MAX_LOG; i++) {
    for (long long j = 0; j < sz; j++) {
      if (i == 0) {
        w[j] = make_pair(make_pair(s[j] - 'a', -1), j);
      } else {
        w[j] = make_pair(
            make_pair(rnk[j][i - 1],
                      (j + (1 << (i - 1)) < sz ? rnk[j + (1 << (i - 1))][i - 1]
                                               : -1)),
            j);
      }
    }
    sort(w, w + sz);
    pair<long long, long long> last = make_pair(-1, -1);
    long long x = -1;
    for (long long j = 0; j < sz; j++) {
      if (last != w[j].first) {
        x++;
        last = w[j].first;
      }
      rnk[w[j].second][i] = x;
    }
  }
  for (long long i = 0; i < sz; i++) {
    sa[rnk[i][MAX_LOG - 1]] = i;
  }
  for (long long i = 0; i < (sz - 1); i++) {
    a[i + 1] = lcp(sa[i], sa[i + 1]);
  }
  long long z = 0, res = 0;
  for (long long i = 1; i <= (sz - 1); i++) {
    long long e = 1;
    while (!stk.empty() && stk.top().first > a[i]) {
      z -= stk.top().first * stk.top().second;
      e += stk.top().second;
      stk.pop();
    }
    z += e * a[i];
    stk.push(make_pair(a[i], e));
    res += z;
  }
  cout << res + ((sz * (sz + 1)) / 2);
}