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;
template <class T>
inline T pow2(T a) {
  return a * a;
}
template <class T>
inline bool mineq(T& a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
const int maxn = (int)2e5 + 10;
string str;
long long p[50][maxn], n, gap, stp;
struct entry {
  int n[2], p;
} l[maxn];
bool cmp(entry a, entry b) {
  if (a.n[0] != b.n[0]) return a.n[0] < b.n[0];
  return a.n[1] < b.n[1];
}
void BuildSA() {
  n = str.size();
  for (int i = 0; i < n; i++) {
    p[0][i] = str[i] - '0';
  }
  for (gap = 1, stp = 1; gap / 2 < n; gap *= 2, stp++) {
    for (int i = 0; i < n; i++) {
      l[i].n[0] = p[stp - 1][i];
      l[i].n[1] = (i + gap < n ? p[stp - 1][i + gap] : -1);
      l[i].p = i;
    }
    sort(l, l + n, cmp);
    for (int i = 0; i < n; i++) {
      p[stp][l[i].p] =
          (i > 0 && l[i].n[0] == l[i - 1].n[0] && l[i].n[1] == l[i - 1].n[1]
               ? p[stp][l[i - 1].p]
               : i);
    }
  }
}
int lcp(int x, int y) {
  int k = 0, ret = 0;
  if (x == y) return n - x;
  for (k = stp - 1; k >= 0 && x < n && y < n; k--) {
    if (p[k][x] == p[k][y]) {
      x += 1 << k;
      y += 1 << k;
      ret += 1 << k;
    }
  }
  return ret;
}
long long num[maxn], h[maxn];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> str;
  BuildSA();
  for (int i = 0; i < n; i++) num[p[stp - 1][i]] = i;
  for (int i = 0; i < n - 1; i++) h[i] = lcp(num[i], num[i + 1]);
  long long ans = (n * (n + 1)) / 2, now = 0;
  vector<pair<long long, long long> > stk;
  stk.push_back(make_pair(-1, -1));
  for (int i = 0; i < n - 1; i++) {
    while (stk.back().first > h[i]) {
      now -=
          stk.back().first * (stk.back().second - stk[stk.size() - 2].second);
      stk.pop_back();
    }
    now += h[i] * (i - stk.back().second);
    ans += now;
    stk.push_back(make_pair(h[i], i));
  }
  cout << ans;
}