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 checkmin(T &a, T b) {
  return (a < b) ? a : a = b;
}
template <class T>
inline T checkmax(T &a, T b) {
  return (a > b) ? a : a = b;
}
template <class T>
T GCD(T a, T b) {
  if (a < 0) return GCD(-a, b);
  if (b < 0) return GCD(a, -b);
  return (a == 0) ? b : GCD(b % a, a);
}
template <class T>
T LCM(T a, T b) {
  if (a < 0) return LCM(-a, b);
  if (b < 0) return LCM(a, -b);
  return (a == 0 || b == 0) ? 0 : a / GCD(a, b) * b;
}
template <class T>
inline T sqr(T X) {
  return X * X;
}
namespace Poor {
const int MaxiN = 100005;
const int LogMaxiN = 18;
const int CharSet = 256;
int N;
char St[MaxiN];
long long Ra[CharSet];
long long X[LogMaxiN][MaxiN];
int SA[MaxiN], H[MaxiN];
int LCP(int A, int B) {
  int Rec = A;
  for (int j = LogMaxiN - 1; j >= 0; --j)
    if (A + (1 << j) <= N && B + (1 << j) <= N && X[j][A] == X[j][B]) {
      A += (1 << j);
      B += (1 << j);
    }
  return A - Rec;
}
bool Cmp(int A, int B) {
  int L = LCP(A, B);
  return A + L == N || (B + L < N && St[A + L] < St[B + L]);
}
long long Solve(int L, int R, int C) {
  int Len = LCP(SA[L], SA[R]);
  long long res =
      (long long)(R - L + 1) * (R - L + 2) / 2LL * (long long)(Len - C);
  if (L == R) return res;
  if (LCP(SA[L], SA[L]) == Len) return res + Solve(L + 1, R, Len);
  if (LCP(SA[R], SA[R]) == Len) return res + Solve(L, R - 1, Len);
  int l = L, r = R;
  while (l < r) {
    int mid = (l + r + 1) >> 1;
    if (LCP(SA[L], SA[mid]) > Len)
      l = mid;
    else
      r = mid - 1;
  }
  res += Solve(L, l, Len) + Solve(l + 1, R, Len);
  return res;
}
void Run() {
  srand(time(NULL));
  gets(St);
  N = strlen(St);
  for (int i = 0; i < CharSet; ++i)
    Ra[i] = (long long)rand() + (((long long)rand()) << 32LL);
  for (int i = 0; i < N; ++i) X[0][i] = Ra[(int)St[i]];
  for (int j = 0; j < LogMaxiN - 1; ++j)
    for (int i = 0; i < N - (1 << j); ++i)
      X[j + 1][i] = (X[j][i] * Ra[j + 1]) ^ (X[j][i + (1 << j)]);
  for (int i = 0; i < N; ++i) SA[i] = i;
  sort(SA, SA + N, Cmp);
  cout << Solve(0, N - 1, 0) << endl;
}
}  // namespace Poor
int main() {
  Poor::Run();
  return 0;
}