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 sufnode;
struct sufbrunch {
  unsigned start;
  unsigned length;
  sufnode *vertex;
  sufbrunch(unsigned _start, unsigned _length, sufnode *_vertex) {
    start = _start;
    length = _length;
    vertex = _vertex;
  }
};
struct sufnode {
  unsigned depth;
  sufnode *parent;
  sufnode *suffix;
  vector<sufbrunch> brunch;
  sufnode(sufnode *_parent, unsigned _depth) {
    parent = _parent;
    suffix = 0;
    depth = _depth;
  }
};
class suftree {
 private:
  unsigned n;
  sufnode *last;
  char *pstr;
  void addsuffix(unsigned start, unsigned fix, sufnode *cnode);
  void add(unsigned start, sufnode *cnode);
  sufnode *split(sufbrunch *b, sufnode *v, unsigned start, unsigned fix) {
    sufnode *node = new sufnode(v, v->depth + fix);
    node->brunch.push_back(
        sufbrunch(b->start + fix, b->length - fix, b->vertex));
    node->brunch.push_back(sufbrunch(
        start, n - start, new sufnode(node, node->depth + n - start)));
    b->length = fix;
    b->vertex = node;
    return node;
  }

 public:
  sufnode *root;
  suftree(char *_pstr) {
    pstr = _pstr;
    last = root = new sufnode(0, 0);
    for (n = 0; pstr[n]; n++) {
    }
    n++;
    root->brunch.push_back(sufbrunch(0, n, new sufnode(root, n)));
    for (unsigned i = 1; i < n; i++) {
      if (last == root)
        add(i, root);
      else if (last->parent == root)
        addsuffix(i, last->depth - 1, root);
      else
        addsuffix(i + last->parent->suffix->depth,
                  last->depth - last->parent->depth, last->parent->suffix);
    }
  }
};
void suftree::add(unsigned start, sufnode *cnode) {
  while (true) {
    vector<sufbrunch>::iterator i;
    for (i = cnode->brunch.begin();
         i != cnode->brunch.end() && pstr[i->start] != pstr[start]; i++) {
    }
    if (i == cnode->brunch.end()) {
      cnode->brunch.push_back(sufbrunch(
          start, n - start, new sufnode(cnode, cnode->depth + n - start)));
      last = cnode;
      break;
    } else {
      unsigned j;
      for (j = 1; j < i->length && pstr[start + j] == pstr[i->start + j]; j++) {
      }
      if (j == i->length) {
        start += i->length;
        cnode = i->vertex;
      } else {
        last = split(&(*i), cnode, start + j, j);
        break;
      }
    }
  }
}
void suftree::addsuffix(unsigned start, unsigned fix, sufnode *cnode) {
  while (fix > 0) {
    vector<sufbrunch>::iterator i;
    for (i = cnode->brunch.begin(); pstr[i->start] != pstr[start]; i++) {
    }
    if (i->length > fix) {
      last = last->suffix = split(&(*i), cnode, start + fix, fix);
      return;
    } else {
      fix -= i->length;
      start += i->length;
      cnode = i->vertex;
    }
  }
  last->suffix = cnode;
  add(start, cnode);
}
unsigned long long res = 0;
int solve(sufnode *node) {
  if (node->brunch.empty()) return 1;
  int r = 0, t;
  for (vector<sufbrunch>::iterator i = node->brunch.begin();
       i != node->brunch.end(); i++) {
    t = solve(i->vertex);
    unsigned long long len = (t == 1 ? i->length - 1 : i->length);
    r += t;
    res += len * t * (t + 1) / 2;
  }
  return r;
}
char s[200000];
int main(void) {
  cin.getline(s, 150000);
  suftree tree(s);
  solve(tree.root);
  cout << res;
  return 0;
}