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;
using db = double;
using ll = long long;
using uint = unsigned int;
using ull = unsigned long long;
using pii = pair<int, int>;
template <class T>
void cmax(T& x, const T& y) {
  if (x < y) x = y;
}
template <class T>
void cmin(T& x, const T& y) {
  if (x > y) x = y;
}
template <class T>
void sort(vector<T>& v) {
  sort(v.begin(), v.end());
}
template <class T>
void reverse(vector<T>& v) {
  reverse(v.begin(), v.end());
}
template <class T>
void unique(vector<T>& v) {
  sort(v.begin(), v.end()), v.erase(unique(v.begin(), v.end()), v.end());
}
inline void reverse(string& s) { reverse(s.begin(), s.end()); }
const int SZ = 1 << 23 | 233;
struct FILEIN {
  char qwq[SZ], *S = qwq, *T = qwq, ch;
  inline char GETC() {
    return (S == T) && (T = (S = qwq) + fread(qwq, 1, SZ, stdin), S == T)
               ? EOF
               : *S++;
  }
  inline FILEIN& operator>>(char& c) {
    while (isspace(c = GETC()))
      ;
    return *this;
  }
  inline FILEIN& operator>>(string& s) {
    s.clear();
    while (isspace(ch = GETC()))
      ;
    if (!~ch) return *this;
    s = ch;
    while (!isspace(ch = GETC()) && ~ch) s += ch;
    return *this;
  }
  inline FILEIN& operator>>(char* str) {
    char* cur = str;
    while (*cur) *cur++ = 0;
    cur = str;
    while (isspace(ch = GETC()))
      ;
    if (!~ch) return *this;
    *cur = ch;
    while (!isspace(ch = GETC()) && ~ch) *++cur = ch;
    *++cur = 0;
    return *this;
  }
  template <class T>
  inline void read(T& x) {
    bool f = 0;
    while ((ch = GETC()) < 48 && ~ch) f ^= (ch == 45);
    x = ~ch ? (ch ^ 48) : 0;
    while ((ch = GETC()) > 47) x = x * 10 + (ch ^ 48);
    x = f ? -x : x;
  }
  inline FILEIN& operator>>(int& x) { return read(x), *this; }
  inline FILEIN& operator>>(ll& x) { return read(x), *this; }
  inline FILEIN& operator>>(uint& x) { return read(x), *this; }
  inline FILEIN& operator>>(ull& x) { return read(x), *this; }
  inline FILEIN& operator>>(double& x) {
    read(x);
    bool f = x < 0;
    x = f ? -x : x;
    if (ch ^ '.') return *this;
    double d = 0.1;
    while ((ch = GETC()) > 47) x += d * (ch ^ 48), d *= .1;
    return x = f ? -x : x, *this;
  }
} in;
struct FILEOUT {
  const static int LIMIT = 1 << 22;
  char quq[SZ], ST[233];
  int sz, O, pw[233];
  FILEOUT() {
    set(7);
    for (register int i = (pw[0] = 1); i <= (9); ++i) pw[i] = pw[i - 1] * 10;
  }
  ~FILEOUT() { flush(); }
  inline void flush() { fwrite(quq, 1, O, stdout), fflush(stdout), O = 0; }
  inline FILEOUT& operator<<(char c) { return quq[O++] = c, *this; }
  inline FILEOUT& operator<<(string str) {
    if (O > LIMIT) flush();
    for (char c : str) quq[O++] = c;
    return *this;
  }
  inline FILEOUT& operator<<(char* str) {
    if (O > LIMIT) flush();
    char* cur = str;
    while (*cur) quq[O++] = (*cur++);
    return *this;
  }
  template <class T>
  void write(T x) {
    if (O > LIMIT) flush();
    if (x < 0) {
      quq[O++] = 45;
      x = -x;
    }
    do {
      ST[++sz] = x % 10 ^ 48;
      x /= 10;
    } while (x);
    while (sz) quq[O++] = ST[sz--];
  }
  inline FILEOUT& operator<<(int x) { return write(x), *this; }
  inline FILEOUT& operator<<(ll x) { return write(x), *this; }
  inline FILEOUT& operator<<(uint x) { return write(x), *this; }
  inline FILEOUT& operator<<(ull x) { return write(x), *this; }
  int len, lft, rig;
  void set(int l) { len = l; }
  inline FILEOUT& operator<<(double x) {
    bool f = x < 0;
    x = f ? -x : x, lft = x, rig = 1. * (x - lft) * pw[len];
    return write(f ? -lft : lft), quq[O++] = '.', write(rig), *this;
  }
} out;
struct Math {
  vector<long long> fac, inv;
  long long mod;
  void set(long long n, long long Mod) {
    fac.resize(n + 1), inv.resize(n + 1), mod = Mod;
    for (register long long i = (fac[0] = 1); i <= (n); ++i)
      fac[i] = fac[i - 1] * i % mod;
    inv[n] = qpow(fac[n], mod - 2);
    for (register long long i = (n - 1); i >= (0); --i)
      inv[i] = inv[i + 1] * (i + 1) % mod;
  }
  long long qpow(long long x, long long y) {
    long long ans = 1;
    for (; y; y >>= 1, x = x * x % mod)
      if (y & 1) ans = ans * x % mod;
    return ans;
  }
  long long C(long long n, long long m) {
    if (n < 0 || m < 0 || n < m) return 0;
    return fac[n] * inv[m] % mod * inv[n - m] % mod;
  }
  long long gcd(long long x, long long y) { return !y ? x : gcd(y, x % y); }
  long long lcm(long long x, long long y) { return x * y / gcd(x, y); }
} math;
const long long maxn = 3e5 + 53;
struct suffix_auto_maton {
  long long las, cnt;
  suffix_auto_maton() { las = cnt = 1; }
  long long ch[maxn][26], fa[maxn], len[maxn];
  long long sz[maxn];
  void ins(long long c, long long pos) {
    long long p = las, np = las = ++cnt;
    len[np] = len[p] + 1, sz[np] = 1;
    for (; p && !ch[p][c]; p = fa[p]) ch[p][c] = np;
    if (!p) {
      fa[np] = 1;
    } else {
      long long q = ch[p][c];
      if (len[q] == len[p] + 1) {
        fa[np] = q;
      } else {
        long long nq = ++cnt;
        memcpy(ch[nq], ch[q], sizeof(ch[q]));
        fa[nq] = fa[q], fa[q] = fa[np] = nq, len[nq] = len[p] + 1;
        for (; p && ch[p][c] == q; p = fa[p]) ch[p][c] = nq;
      }
    }
  }
  void ins(char* S) {
    char* Cur = S;
    long long qwq = 0;
    while (*Cur) ins((*Cur++) - 'a', ++qwq);
  }
  vector<long long> g[maxn];
  long long ans = 0;
  void dfs(long long u) {
    for (long long v : g[u]) {
      dfs(v);
      sz[u] += sz[v];
    }
    ans += sz[u] * (sz[u] + 1) / 2 * (len[u] - len[fa[u]]);
  }
  void build() {
    for (register long long i = (2); i <= (cnt); ++i) g[fa[i]].emplace_back(i);
  }
} sam;
char s[maxn];
signed main() {
  in >> s;
  sam.ins(s);
  sam.build();
  sam.dfs(1);
  out << sam.ans << '\n';
  return 0;
}