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;
char s[100048];
int len, k;
int sa[100048], tmp[100048], rnk[100048], lcp[100048];
inline bool compare_sa(int first, int second) {
  if (rnk[first] != rnk[second]) return rnk[first] < rnk[second];
  int tmp1 = first + k <= len ? rnk[first + k] : -1,
      tmp2 = second + k <= len ? rnk[second + k] : -1;
  return tmp1 < tmp2;
}
inline void construct_sa() {
  int i, cnt;
  for (i = 1; i <= len; i++) sa[i] = i, rnk[i] = s[i];
  for (k = 0; k <= len; k == 0 ? k++ : k <<= 1) {
    sort(sa + 1, sa + len + 1, compare_sa);
    tmp[sa[1]] = 1;
    cnt = 0;
    for (i = 2; i <= len; i++) {
      tmp[sa[i]] = tmp[sa[i - 1]] + (compare_sa(sa[i - 1], sa[i]) ? 1 : 0);
      cnt += (tmp[sa[i]] == tmp[sa[i - 1]] ? 0 : 1);
    }
    for (i = 1; i <= len; i++) rnk[i] = tmp[i];
    if (cnt >= len - 1) break;
  }
}
inline void construct_lcp() {
  int i, j, h = 0;
  for (i = 1; i <= len; i++) rnk[sa[i]] = i;
  for (i = 1; i <= len; i++) {
    j = sa[rnk[i] - 1];
    if (h) h--;
    while (i + h <= len && j + h <= len && s[i + h] == s[j + h]) h++;
    lcp[rnk[i] - 1] = h;
  }
}
pair<int, int> sta[100048];
int stot;
int cnt;
long long curans;
int main() {
  scanf("%s", s + 1);
  len = strlen(s + 1);
  construct_sa();
  construct_lcp();
  long long ans = (long long)len * (len + 1) / 2;
  stot = 0;
  curans = 0;
  for (register int i = len - 1; i; i--) {
    cnt = 1;
    while (stot && sta[stot].first > lcp[i])
      curans -= (long long)sta[stot].first * sta[stot].second,
          cnt += sta[stot].second, stot--;
    curans += (long long)lcp[i] * cnt;
    ans += curans;
    sta[++stot] = make_pair(lcp[i], cnt);
  }
  printf("%lld\n", ans);
  return 0;
}