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 MAXN = 1e5;
char s[MAXN + 48];
int n;
stack<pair<long long, long long> > sta;
namespace Suffix_Array {
int cnt[MAXN + 48], fir[MAXN + 48], sec[MAXN + 48], sa[MAXN + 48],
    tmp[MAXN + 48];
int rnk[MAXN + 48], lcp[MAXN + 48];
inline bool compare_sa(int first, int second, int k) {
  if (fir[first] != fir[second]) return fir[first] < fir[second];
  int tmp1 = (first + k <= n ? fir[first + k] : -1),
      tmp2 = (second + k <= n ? fir[second + k] : -1);
  return tmp1 < tmp2;
}
inline void construct_sa(char s[]) {
  int maxind = 'z';
  memset(cnt + 1, 0, maxind << 2);
  for (register int i = 1; i <= n; i++) cnt[s[i]]++;
  for (register int i = 1; i <= maxind; i++) cnt[i] += cnt[i - 1];
  for (register int i = n; i >= 1; i--) sa[cnt[s[i]]--] = i;
  fir[sa[1]] = 1;
  for (register int i = 2; i <= n; i++)
    fir[sa[i]] = fir[sa[i - 1]] + (s[sa[i]] != s[sa[i - 1]]);
  for (register int len = 1; len <= n; len <<= 1) {
    int tot = 0;
    for (register int i = n - len + 1; i <= n; i++) sec[++tot] = i;
    for (register int i = 1; i <= n; i++)
      if (sa[i] > len) sec[++tot] = sa[i] - len;
    memset(cnt + 1, 0, maxind << 2);
    for (register int i = 1; i <= n; i++) cnt[fir[sec[i]]]++;
    for (register int i = 1; i <= maxind; i++) cnt[i] += cnt[i - 1];
    for (register int i = n; i >= 1; i--) sa[cnt[fir[sec[i]]]--] = sec[i];
    tmp[sa[1]] = tot = 1;
    for (register int i = 2; i <= n; i++)
      tmp[sa[i]] = tmp[sa[i - 1]] + compare_sa(sa[i - 1], sa[i], len);
    memcpy(fir + 1, tmp + 1, n << 2);
    maxind = fir[sa[n]];
    if (maxind >= n) break;
  }
}
inline void construct_lcp() {
  int h = 0;
  for (register int i = 1; i <= n; i++) rnk[sa[i]] = i;
  for (register int i = 1; i <= n; i++) {
    int j = sa[rnk[i] - 1];
    if (h) h--;
    while (i + h <= n && j + h <= n && s[i + h] == s[j + h]) h++;
    lcp[rnk[i] - 1] = h;
  }
}
}  // namespace Suffix_Array
int main() {
  scanf("%s", s + 1);
  n = strlen(s + 1);
  using namespace Suffix_Array;
  construct_sa(s);
  construct_lcp();
  long long ans = 1ll * (n + 1) * n / 2, curans = 0, curcnt;
  for (int i = n - 1; i >= 1; i--) {
    curcnt = 1;
    while (!sta.empty() && lcp[i] < sta.top().first)
      curcnt += sta.top().second, curans -= sta.top().first * sta.top().second,
          sta.pop();
    curans += 1ll * lcp[i] * curcnt;
    ans += curans;
    sta.push(make_pair(lcp[i], curcnt));
  }
  printf("%lld\n", ans);
  return 0;
}