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;
int n, t;
int p[150000], r[150000], h[150000];
char s[150000];
bool comp(int i, int j) { return p[i + t] < p[j + t]; }
void suff_arr() {
  int bc[256];
  for (int i = 0; i < 256; i++) bc[i] = 0;
  for (int i = 0; i < n; i++) ++bc[s[i]];
  for (int i = 1; i < 256; i++) bc[i] += bc[i - 1];
  for (int i = 0; i < n; i++) r[--bc[s[i]]] = i;
  for (int i = 0; i < n; i++) p[i] = bc[s[i]];
  for (t = 1; t < n; t *= 2) {
    for (int i = 0, j = 1; j < n; i = j++) {
      while (j < n && p[r[j]] == p[r[i]]) j++;
      if (j - i == 1) continue;
      int *ini = r + i, *fin = r + j;
      sort(ini, fin, comp);
      int pri = p[*ini + t], num = i, pk;
      for (; ini < fin; p[*ini++] = num) {
        if (((pk = p[*ini + t]) == pri) || (i <= pri && pk < j)) {
        } else
          pri = pk, num = ini - r;
      }
    }
  }
}
void lcp() {
  int tam = 0, i, j;
  for (i = 0; i < n; i++)
    if (p[i] > 0) {
      j = r[p[i] - 1];
      while (s[i + tam] == s[j + tam]) ++tam;
      h[p[i] - 1] = tam;
      if (tam > 0) --tam;
    }
  h[n - 1] = 0;
}
pair<int, int> ss[200000];
int sz = 0;
long long C[200000];
int main() {
  scanf("%s", s);
  n = strlen(s);
  s[n++] = '$';
  suff_arr();
  lcp();
  long long res = 0;
  for (long long i = 0; i < 200000; i++) C[i] = i * (i + 1) / 2;
  ss[sz++] = make_pair(0, 0);
  for (int i = 1; i < n; i++) {
    res += n - r[i] - 1 - max(h[i], h[i - 1]);
    while (ss[sz - 1].first > h[i])
      if (h[i] <= ss[sz - 2].first) {
        res += C[i - ss[sz - 1].second + 1] *
               (ss[sz - 1].first - ss[sz - 2].first);
        sz--;
      } else {
        res += C[i - ss[sz - 1].second + 1] * (ss[sz - 1].first - h[i]);
        ss[sz - 1].first = h[i];
      }
    if (ss[sz - 1].first != h[i]) ss[sz++] = make_pair(h[i], i);
  }
  cout << res << endl;
}