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;
namespace SA {
int wa[1000005], wb[1000005], wv[1000005], ws[1000005];
inline void SA(char* s, int* sa, int n, int m) {
  int *x = wa, *y = wb, i, j, p;
  for (i = 0; i <= m; i++) ws[i] = 0;
  for (i = 1; i <= n; i++) ws[x[i] = s[i]]++;
  for (i = 1; i <= m; i++) ws[i] += ws[i - 1];
  for (i = n; i; i--) sa[ws[x[i]]--] = i;
  for (j = 1, p = 0; p <= n; j <<= 1, m = p) {
    p = 0;
    for (i = n - j + 1; i <= n; i++) y[++p] = i;
    for (i = 1; i <= n; i++)
      if (sa[i] > j) y[++p] = sa[i] - j;
    for (i = 1; i <= m; i++) ws[i] = 0;
    for (i = 1; i <= n; i++) wv[i] = x[y[i]];
    for (i = 1; i <= n; i++) ws[x[i]]++;
    for (i = 1; i <= m; i++) ws[i] += ws[i - 1];
    for (i = n; i; i--) sa[ws[wv[i]]--] = y[i];
    swap(x, y), p = 2, x[sa[1]] = 1;
    for (i = 2; i <= n; i++)
      x[sa[i]] = (y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + j] == y[sa[i] + j])
                     ? p - 1
                     : p++;
  }
}
int rnk[1000005], height[1000005];
inline void Ht(char* r, int* sa, int n) {
  for (int i = 1; i <= n; i++) rnk[sa[i]] = i;
  for (int i = 1, u = 0; i <= n; height[rnk[i++]] = u)
    for (u -= bool(u); r[i + u] == r[sa[rnk[i] - 1] + u]; u++)
      ;
}
}  // namespace SA
using namespace SA;
char ch[2000005];
int sa[2000005], n;
long long ans, cur;
vector<pair<int, int> > st;
int main() {
  cin >> (ch + 1);
  n = strlen(ch + 1);
  ans += 1ll * n * (n + 1) / 2;
  SA::SA(ch, sa, n, 128), Ht(ch, sa, n);
  for (int i = n; i > 1; i--) {
    int tmp = 0;
    while (st.size() && st.back().first > height[i])
      cur += 1ll * st.back().first * st.back().second, tmp += st.back().second,
          st.pop_back();
    cur -= 1ll * height[i] * (tmp + 1);
    ans -= cur;
    st.push_back(pair<int, int>(height[i], tmp + 1));
  }
  cout << ans;
}