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 Suffixautomaton {
  struct Node {
    int deep, fail, id;
    int next[30];
    void clear() {
      deep = fail = 0;
      memset(next, 0, sizeof(next));
    }
  };
  int size, endp, ans;
  Node node[2 * 600000];
  void init() {
    for (int i = 0; i < 30; i++) node[0].next[i] = 1;
    node[0].deep = -1;
    node[1].clear();
    size = 2;
    endp = 1;
    ans = 0;
  }
  void insert(int c, int id) {
    int p, p1, p2;
    p = size++;
    node[p].clear();
    node[p].deep = node[endp].deep + 1;
    node[p].id = id;
    while (node[endp].next[c] == 0) {
      node[endp].next[c] = p;
      endp = node[endp].fail;
    }
    p1 = node[endp].next[c];
    if (node[p1].deep == node[endp].deep + 1)
      node[p].fail = p1;
    else {
      p2 = size++;
      node[p2] = node[p1];
      node[p].fail = node[p1].fail = p2;
      node[p2].deep = node[endp].deep + 1;
      while (node[endp].next[c] == p1) {
        node[endp].next[c] = p2;
        endp = node[endp].fail;
      }
    }
    endp = p;
  }
  int cnt[2 * 600000], st[2 * 600000];
  inline int getid(char &c) {
    if (islower(c)) return c - 'a';
    return 26 + c - 'A';
  }
  int path[600000], val[600000];
  long long build(char *s, int len) {
    int i, j, k, x;
    for (i = 0; i < len; i++) insert(getid(s[i]), i);
    for (i = 0; i <= len; i++) cnt[i] = 0;
    for (i = 1; i < size; i++) cnt[node[i].deep]++;
    for (i = 1; i <= len; i++) cnt[i] += cnt[i - 1];
    for (i = 1; i < size; i++) st[cnt[node[i].deep]--] = i;
    for (i = size - 1; i > 0; i--) {
      x = st[i];
      path[x] = 0;
      for (k = 0; k < 26; k++) {
        if (node[x].next[k] == 0) continue;
        path[x] += path[node[x].next[k]];
      }
      if (node[x].next[26]) path[x]++;
    }
    for (i = 1; i < size; i++) val[i] = 0;
    val[1] = 1;
    for (i = 1; i < size; i++) {
      x = st[i];
      for (k = 0; k < 26; k++) {
        if (node[x].next[k] == 0) continue;
        val[node[x].next[k]] += val[x];
      }
    }
    long long ret = 0;
    for (i = 2; i < size; i++) {
      ret += 1LL * val[i] * path[i] * (path[i] + 1) / 2;
    }
    return ret;
  }
} sam;
char s[600000], t[600000];
int main() {
  scanf("%s", s);
  strcat(s, "A");
  sam.init();
  int len = strlen(s);
  printf("%I64d\n", sam.build(s, len));
  return 0;
}