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;
struct r_e_d {
  inline int gti() {
    int x = 0, w = 1;
    char ch = getchar();
    while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
    if (ch == '-') w = -1, ch = getchar();
    while (ch >= '0' && ch <= '9')
      x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    return x * w;
  }
  inline long long gtl() {
    long long x = 0, w = 1;
    char ch = getchar();
    while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
    if (ch == '-') w = -1, ch = getchar();
    while (ch >= '0' && ch <= '9')
      x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    return x * w;
  }
  inline string gts() {
    string S;
    char ch = getchar();
    while (ch == ' ' || ch == '\n' || ch == '\r') ch = getchar();
    while (ch != ' ' && ch != '\n' && ch != '\r')
      S.push_back(ch), ch = getchar();
    return S;
  }
} RD;
string S;
stack<pair<int, int> > T;
long long as;
struct suffix_array {
  int sa[100005], rk[100005], ha[100005], hs[100005], lb[100005], bn[100005],
      sz, ls;
  void build(string S) {
    ls = S.size() - 1;
    sz = max(255, ls);
    for (int i = (1); i <= (ls); ++i) rk[i] = S[i];
    for (int i = (1); i <= (sz); ++i) bn[i] = 0;
    for (int i = (1); i <= (ls); ++i) ++bn[rk[i]];
    for (int i = (1); i <= (sz); ++i) bn[i] += bn[i - 1];
    for (int i = (1); i <= (ls); ++i) sa[bn[rk[i]]--] = i;
    for (int j = 1; j <= ls; j <<= 1) {
      int tt = 0;
      for (int i = (ls - j + 1); i <= (ls); ++i) lb[++tt] = i;
      for (int i = (1); i <= (ls); ++i)
        if (sa[i] - j >= 1) lb[++tt] = sa[i] - j;
      for (int i = (1); i <= (sz); ++i) bn[i] = 0;
      for (int i = (1); i <= (ls); ++i) ++bn[rk[i]];
      for (int i = (1); i <= (sz); ++i) bn[i] += bn[i - 1];
      for (int i = (ls); i >= (1); --i) sa[bn[rk[lb[i]]]--] = lb[i];
      lb[sa[1]] = 1;
      tt = 1;
      for (int i = (2); i <= (ls); ++i)
        lb[sa[i]] =
            (rk[sa[i]] == rk[sa[i - 1]] && rk[sa[i] + j] == rk[sa[i - 1] + j])
                ? tt
                : ++tt;
      for (int i = (1); i <= (ls); ++i) rk[i] = lb[i];
      if (tt == ls) break;
    }
    for (int i = (1); i <= (ls); ++i) {
      hs[i] = max(hs[i - 1] - 1, 0);
      while (S[i + hs[i]] == S[sa[rk[i] - 1] + hs[i]]) ++hs[i];
      ha[rk[i]] = hs[i];
    }
    for (int i = (ls); i >= (1); --i) hs[i] = hs[i - 1];
  }
  void work() {
    T.push(make_pair(0, 0));
    for (int i = (1); i <= (ls + 1); ++i) {
      while (T.size() && T.top().first > ha[i]) {
        int zi = T.top().first;
        int le = T.top().second;
        T.pop();
        int lm = max(T.top().first, ha[i]);
        as += 1ll * (le + 1) * le / 2 * (zi - lm);
        if (lm == ha[i]) T.push(make_pair(ha[i], 0));
        T.top().second += le;
      }
      T.push(make_pair(ls - sa[i] + 1, 1));
    }
  }
} SA;
int main() {
  S = RD.gts();
  S = ' ' + S;
  SA.build(S);
  SA.work();
  printf("%lld\n", as);
  return 0;
}