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 double pi = acos(-1.0);
const double eps = 1e-9;
const int INF = 1E9;
const int MAXN = 200500;
const int ALPH = 27;
struct node {
  int L, len, link;
  int go[ALPH];
  node(int _L = 0, int _len = 0) {
    L = _L;
    len = _len;
    link = 0;
    memset(go, 0, sizeof(go));
  }
};
int n;
char s[MAXN];
int sz;
node a[MAXN];
int curV, curPos;
int addNode(int L, int len) {
  a[sz] = node(L, len);
  return sz++;
}
void goDown() {
  while (curPos > a[a[curV].go[s[n - curPos] - 'a']].len) {
    curV = a[curV].go[s[n - curPos] - 'a'];
    curPos -= a[curV].len;
  }
}
void extend(char c) {
  s[n++] = c;
  curPos++;
  int last = 0;
  while (curPos > 0) {
    goDown();
    int edge = s[n - curPos] - 'a';
    int &v = a[curV].go[edge];
    char d = s[a[v].L + curPos - 1];
    if (v == 0) {
      v = addNode(n - curPos, INF);
      a[last].link = curV;
      last = 0;
    } else if (c == d) {
      a[last].link = curV;
      return;
    } else {
      int u = addNode(a[v].L, curPos - 1);
      a[u].go[c - 'a'] = addNode(n - 1, INF);
      a[u].go[d - 'a'] = v;
      a[v].L += curPos - 1;
      if (a[v].len != INF) a[v].len -= curPos - 1;
      v = u;
      a[last].link = u;
      last = u;
    }
    if (curV == 0)
      curPos--;
    else
      curV = a[curV].link;
  }
}
void initSuffixTree() {
  n = 0;
  sz = 1;
  a[0] = node(0, INF);
  curV = curPos = 0;
}
string S;
long long ans;
int sumLen = 0;
int cnt[MAXN];
void dfs(int v) {
  bool leaf = 1;
  for (int i = 0; i < (int)(ALPH); i++) {
    int w = a[v].go[i];
    if (w != 0) {
      leaf = 0;
      dfs(w);
      ans += 1ll * a[w].len * cnt[w] * (cnt[w] + 1) / 2;
      cnt[v] += cnt[w];
    }
  }
  if (leaf) cnt[v] = 1;
}
int main() {
  initSuffixTree();
  cin >> S;
  for (int i = 0; i < (int)(S.size()); i++) extend(S[i]);
  extend('a' + ALPH - 1);
  for (int i = 0; i < (int)(sz); i++)
    a[i].len = min(a[i].len, (int)S.size() - a[i].L);
  ans = 0;
  dfs(0);
  cout << ans << '\n';
  return 0;
}