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 debugger {
  template <typename T>
  debugger &operator,(const T &v) {
    cerr << v << "\t";
    return *this;
  }
} dbg;
template <class T>
void setmax(T &a, T b) {
  if (a < b) a = b;
}
template <class T>
void setmin(T &a, T b) {
  if (b < a) a = b;
}
template <class T>
T Abs(T x) {
  return x > 0 ? x : -x;
}
template <class T>
inline T sqr(T x) {
  return x * x;
}
template <class T>
inline T Mod(T n, T m) {
  return (n % m + m) % m;
}
template <class T>
string toString(T n) {
  ostringstream oss;
  oss << n;
  oss.flush();
  return oss.str();
}
int toInt(string s) {
  int r = 0;
  istringstream sin(s);
  sin >> r;
  return r;
}
bool isVowel(char ch) {
  ch = tolower(ch);
  if (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u')
    return true;
  return false;
}
bool isUpper(char c) { return c >= 'A' && c <= 'Z'; }
bool isLower(char c) { return c >= 'a' && c <= 'z'; }
long long Pow(long long B, long long P) {
  long long R = 1;
  while (P > 0) {
    if (P % 2 == 1) R = (R * B);
    P /= 2;
    B = (B * B);
  }
  return R;
}
int BigMod(long long B, long long P, long long M) {
  long long R = 1;
  while (P > 0) {
    if (P % 2 == 1) {
      R = (R * B) % M;
    }
    P /= 2;
    B = (B * B) % M;
  }
  return (int)R;
}
void binprint(long long mask, long long n) {
  long long i;
  string s = "";
  do {
    s += (mask % 2 + '0');
    mask /= 2;
  } while (mask);
  reverse(s.begin(), s.end());
  s = string(max(n - (int)s.size(), 0LL), '0') + s;
  for (i = (int)s.size() - n; i < (int)s.size(); i++) printf("%c", s[i]);
  printf("\n");
}
void ASCII_Chart() {
  int i, j, k;
  printf("ASCII Chart:(30-129)\n");
  for (i = 30; i < 50; i++) {
    for (j = 0; j < 5; j++) {
      k = i + j * 20;
      printf("%3d---> '%c'   ", k, k);
    }
    printf("\n");
  }
}
struct state {
  int len, link;
  bool clone;
  int child[26];
};
state T[2 * 110000];
int sz, last;
void Initialize(int N) {
  int i;
  for (i = 0; i < N; i++) {
    T[i].len = 0;
    T[i].link = -1;
    memset(T[i].child, 0, sizeof(T[i].child));
  }
  sz = 1;
  last = 0;
}
void add_char(char ch) {
  int cur = sz++;
  T[cur].len = T[last].len + 1;
  int p;
  for (p = last; p != -1 && T[p].child[ch] == 0; p = T[p].link) {
    T[p].child[ch] = cur;
  }
  if (p == -1)
    T[cur].link = 0;
  else {
    int q = T[p].child[ch];
    if (T[p].len + 1 == T[q].len)
      T[cur].link = q;
    else {
      int clone = sz++;
      T[clone].link = T[q].link;
      T[clone].len = T[p].len + 1;
      memcpy(T[clone].child, T[q].child, sizeof T[q].child);
      for (p = p; p != -1 && T[p].child[ch] == q; p = T[p].link)
        T[p].child[ch] = clone;
      T[q].link = T[cur].link = clone;
      T[clone].clone = true;
    }
  }
  last = cur;
}
vector<int> incoming[2 * 110000], rev_par[2 * 110000];
void PreProcess() {
  int i, j;
  for (i = 0; i < sz; i++) {
    for (j = 0; j < 26; j++) {
      if (T[i].child[j]) incoming[T[i].child[j]].push_back(i);
    }
    if (i) rev_par[T[i].link].push_back(i);
  }
}
long long dp1[2 * 110000], dp2[2 * 110000];
long long rec1(int curNode) {
  if (curNode == 0) return 1;
  long long &ret = dp1[curNode];
  if (ret != -1) return ret;
  ret = 0;
  int i;
  for (i = 0; i < (int)incoming[curNode].size(); i++) {
    ret += rec1(incoming[curNode][i]);
  }
  return ret;
}
long long rec2(int curNode) {
  long long &ret = dp2[curNode];
  if (ret != -1) return ret;
  ret = !T[curNode].clone;
  int i;
  for (i = 0; i < (int)rev_par[curNode].size(); i++) {
    ret += rec2(rev_par[curNode][i]);
  }
  return ret;
}
char str[110000];
int main() {
  int test, Case = 1, i, j, k, len;
  long long ans, val1, val2;
  scanf("%s", str);
  len = strlen(str);
  Initialize(1);
  for (i = 0; i < len; i++) add_char(str[i] - 'a');
  PreProcess();
  ans = 0;
  memset(dp1, -1, sizeof(dp1));
  memset(dp2, -1, sizeof(dp2));
  for (i = 0; i < sz; i++) {
    val1 = rec1(i);
    val2 = rec2(i) - 1;
    ans += val1 * ((val2 * (val2 + 1)) / 2);
  }
  cout << ans << endl;
  return 0;
}