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 = 100000;
char s[N + 2];
int sa[N + 2], sa2[N + 2], r[N + 2], r2[N + 2], c[N + 2];
int n, a = 128;
int lcp[N + 2], rsa[N + 2];
vector<pair<int, int>> v;
long long ans = 0;
void merge(int x, int y) {
  if (v[x].first != v[y].first) return;
  v[x].second += v[y].second;
  v.erase(v.begin() + y);
}
void reduce(int x, int val) {
  ans += ((long long)v[x].first - val) * v[x].second * (v[x].second + 1);
  v[x].first = val;
}
int main() {
  scanf("%s", s);
  n = strlen(s);
  for (int i = 0; i < n; i++) c[r[i] = s[i]]++;
  for (int i = 1; i < a; i++) c[i] += c[i - 1];
  for (int i = n - 1; i >= 0; i--) sa[--c[r[i]]] = i;
  for (int l = 1; l < n; l *= 2) {
    int p = 0;
    for (int i = n - l; i < n; i++) sa2[p++] = i;
    for (int i = 0; i < n; i++)
      if (sa[i] - l >= 0) sa2[p++] = sa[i] - l;
    for (int i = 0; i < a; i++) c[i] = 0;
    for (int i = 0; i < n; i++) c[r[i]]++;
    for (int i = 1; i < a; i++) c[i] += c[i - 1];
    for (int i = n - 1; i >= 0; i--) sa[--c[r[sa2[i]]]] = sa2[i];
    r2[sa[0]] = 0;
    for (int i = 1; i < n; i++) {
      r2[sa[i]] = r2[sa[i - 1]] + 1;
      if (r[sa[i - 1]] == r[sa[i]] && sa[i - 1] + l < n &&
          r[sa[i - 1] + l] == r[sa[i] + l])
        r2[sa[i]]--;
    }
    for (int i = 0; i < n; i++) swap(r[i], r2[i]);
    a = r[sa[n - 1]] + 1;
    if (a == n) break;
  }
  for (int i = 0; i < n; i++) rsa[sa[i]] = i;
  for (int i = 0, k = 0; i < n; i++, k = max(0, k - 1)) {
    if (rsa[i] == n - 1) {
      lcp[rsa[i]] = k = 0;
      continue;
    }
    int j = sa[rsa[i] + 1];
    while (max(i, j) + k < n && s[i + k] == s[j + k]) k++;
    lcp[rsa[i]] = k;
  }
  for (int i = 0; i < n; i++) {
    v.push_back({lcp[i], 1});
    while (1) {
      if (v.size() == 1) break;
      if (v.size() == 2) {
        if (v[0].first == v[1].first)
          merge(0, 1);
        else if (v[0].first > v[1].first) {
          reduce(0, v[1].first);
          merge(0, 1);
        }
        break;
      }
      int x = v.size() - 3;
      if (v[x + 1].first < v[x + 2].first)
        break;
      else if (v[x + 1].first == v[x + 2].first)
        merge(x + 1, x + 2);
      else {
        reduce(x + 1, max(v[x].first, v[x + 2].first));
        merge(x, x + 1);
      }
    }
    if (v.back().first == 0) v.pop_back();
  }
  ans += (long long)n * (n + 1);
  ans /= 2;
  printf("%lld\n", ans);
}