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;
inline long long getint() {
  long long _x = 0, _tmp = 1;
  char _tc = getchar();
  while ((_tc < '0' || _tc > '9') && _tc != '-') _tc = getchar();
  if (_tc == '-') _tc = getchar(), _tmp = -1;
  while (_tc >= '0' && _tc <= '9') _x *= 10, _x += (_tc - '0'), _tc = getchar();
  return _x * _tmp;
}
long long mypow(long long _a, long long _x, long long _mod) {
  if (_x == 0) return 1ll;
  long long _tmp = mypow(_a, _x / 2, _mod);
  _tmp = (_tmp * _tmp) % _mod;
  if (_x & 1) _tmp = (_tmp * _a) % _mod;
  return _tmp;
}
inline long long add(long long _x, long long _y,
                     long long _mod = 1000000007ll) {
  long long _ = _x + _y;
  if (_ >= _mod) _ -= _mod;
  return _;
}
inline long long sub(long long _x, long long _y,
                     long long _mod = 1000000007ll) {
  long long _ = _x - _y;
  if (_ < 0) _ += _mod;
  return _;
}
inline long long mul(long long _x, long long _y,
                     long long _mod = 1000000007ll) {
  long long _ = _x * _y;
  if (_ >= _mod) _ %= _mod;
  return _;
}
inline bool equal(double _x, double _y) {
  return _x > _y - 1e-9 && _x < _y + 1e-9;
}
int __ = 1, _cs;
struct SA {
  static const int MXN = 300010;
  bool _t[MXN * 2];
  int _s[MXN * 2], _sa[MXN * 2], _c[MXN * 2], x[MXN], _p[MXN], _q[MXN * 2],
      hei[MXN], r[MXN];
  int operator[](int i) { return _sa[i]; }
  void build(int *s, int n, int m) {
    memcpy(_s, s, sizeof(int) * n);
    sais(_s, _sa, _p, _q, _t, _c, n, m);
    mkhei(n);
  }
  void mkhei(int n) {
    for (int i = 0; i < int(n); i++) r[_sa[i]] = i;
    hei[0] = 0;
    for (int i = 0; i < int(n); i++)
      if (r[i]) {
        int ans = i > 0 ? max(hei[r[i - 1]] - 1, 0) : 0;
        while (_s[i + ans] == _s[_sa[r[i] - 1] + ans]) ans++;
        hei[r[i]] = ans;
      }
  }
  void sais(int *s, int *sa, int *p, int *q, bool *t, int *c, int n, int z) {
    bool uniq = t[n - 1] = true, neq;
    int nn = 0, nmxz = -1, *nsa = sa + n, *ns = s + n, lst = -1;
    memset((c), 0, z * sizeof(*(c)));
    for (int i = 0; i < int(n); i++) uniq &= ++c[s[i]] < 2;
    for (int i = 0; i < int(z - 1); i++) c[i + 1] += c[i];
    if (uniq) {
      for (int i = 0; i < int(n); i++) sa[--c[s[i]]] = i;
      return;
    }
    for (int i = n - 2; i >= 0; i--)
      t[i] = (s[i] == s[i + 1] ? t[i + 1] : s[i] < s[i + 1]);
    memset((sa), 0, n * sizeof(*(sa)));
    memcpy(x, c, sizeof(int) * z);
    for (int i = (1); i <= int(n - 1); i++)
      if (t[i] && !t[i - 1]) sa[--x[s[i]]] = p[q[i] = nn++] = i;
    memcpy(x + 1, c, sizeof(int) * (z - 1));
    for (int i = 0; i < int(n); i++)
      if (sa[i] && !t[sa[i] - 1]) sa[x[s[sa[i] - 1]]++] = sa[i] - 1;
    memcpy(x, c, sizeof(int) * z);
    for (int i = n - 1; i >= 0; i--)
      if (sa[i] && t[sa[i] - 1]) sa[--x[s[sa[i] - 1]]] = sa[i] - 1;
    ;
    for (int i = 0; i < int(n); i++)
      if (sa[i] && t[sa[i]] && !t[sa[i] - 1]) {
        neq = lst < 0 || memcmp(s + sa[i], s + lst,
                                (p[q[sa[i]] + 1] - sa[i]) * sizeof(int));
        ns[q[lst = sa[i]]] = nmxz += neq;
      }
    sais(ns, nsa, p + nn, q + n, t + n, c + z, nn, nmxz + 1);
    memset((sa), 0, n * sizeof(*(sa)));
    memcpy(x, c, sizeof(int) * z);
    for (int i = nn - 1; i >= 0; i--) sa[--x[s[p[nsa[i]]]]] = p[nsa[i]];
    memcpy(x + 1, c, sizeof(int) * (z - 1));
    for (int i = 0; i < int(n); i++)
      if (sa[i] && !t[sa[i] - 1]) sa[x[s[sa[i] - 1]]++] = sa[i] - 1;
    memcpy(x, c, sizeof(int) * z);
    for (int i = n - 1; i >= 0; i--)
      if (sa[i] && t[sa[i] - 1]) sa[--x[s[sa[i] - 1]]] = sa[i] - 1;
    ;
  }
} sa;
int h[101010], s[101010];
void suffix_array(int *ip, int len) {
  ip[len++] = 0;
  sa.build(ip, len, 128);
  for (int i = 0; i < len; i++) {
    h[i] = sa.hei[i + 1];
    s[i] = sa._sa[i + 1];
  }
}
long long st[101010 << 2], ad[101010 << 2], tg[101010 << 2];
inline void push(int no, int l, int r) {
  if (ad[no] || tg[no]) {
    if (l < r) {
      if (tg[no]) {
        tg[(no << 1)] = tg[(1 + (no << 1))] = 1;
        ad[(no << 1)] = ad[(1 + (no << 1))] = 0;
        st[(no << 1)] = ((l + r) >> 1) - l + 1;
        st[(1 + (no << 1))] = r - ((l + r) >> 1);
      }
      if (ad[no]) {
        ad[(no << 1)] += ad[no];
        ad[(1 + (no << 1))] += ad[no];
        st[(no << 1)] += (((l + r) >> 1) - l + 1) * ad[no];
        st[(1 + (no << 1))] += (r - ((l + r) >> 1)) * ad[no];
      }
    }
  }
  ad[no] = tg[no] = 0;
}
inline void pull(int no) { st[no] = st[(no << 1)] + st[(1 + (no << 1))]; }
void Add(int no, int l, int r, int ql, int qr) {
  if (l > qr || r < ql) return;
  push(no, l, r);
  if (ql <= l && r <= qr) {
    ad[no]++;
    st[no] += r - l + 1;
    return;
  }
  Add((no << 1), l, ((l + r) >> 1), ql, qr);
  Add((1 + (no << 1)), ((l + r) >> 1) + 1, r, ql, qr);
  pull(no);
}
void Tag(int no, int l, int r, int ql, int qr) {
  if (l > qr || r < ql) return;
  push(no, l, r);
  if (ql <= l && r <= qr) {
    tg[no] = 1;
    ad[no] = 0;
    st[no] = r - l + 1;
    return;
  }
  Tag((no << 1), l, ((l + r) >> 1), ql, qr);
  Tag((1 + (no << 1)), ((l + r) >> 1) + 1, r, ql, qr);
  pull(no);
}
long long query(int no, int l, int r, int ql, int qr) {
  if (l > qr || r < ql || ql > qr) return 0;
  push(no, l, r);
  if (ql <= l && r <= qr) return st[no];
  return query((no << 1), l, ((l + r) >> 1), ql, qr) +
         query((1 + (no << 1)), ((l + r) >> 1) + 1, r, ql, qr);
}
char c[101010];
int vl[101010], len, l[101010];
void build() {}
void init() {
  scanf("%s", c);
  len = strlen(c);
  for (int i = 0; i < len; i++) vl[i] = c[i] - 'a' + 1;
  suffix_array(vl, len);
  for (int i = 0; i < len; i++) l[i] = len - s[i];
}
void solve() {
  long long ans = l[0];
  Tag(1, 1, len, 1, l[0]);
  for (int i = 1; i < len; i++) {
    if (h[i]) Add(1, 1, len, 1, h[i]);
    if (h[i] < l[i]) Tag(1, 1, len, h[i] + 1, l[i]);
    ans += query(1, 1, len, 1, l[i]);
  }
  cout << ans << endl;
}
int main() {
  build();
  while (__--) {
    init();
    solve();
  }
}