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 int inf = 1e9;
const int MAXN = 1e6;
char s[MAXN];
map<int, int> to[MAXN];
int len[MAXN], adla[MAXN], link[MAXN];
int subCnt[MAXN];
int node, pos;
int sz = 1, n = 0;
string a;
int make_node(int _pos, int _len) {
  adla[sz] = _pos;
  len[sz] = _len;
  return sz++;
}
void go_edge() {
  while (pos > len[to[node][s[n - pos]]]) {
    node = to[node][s[n - pos]];
    pos -= len[node];
  }
}
void add_letter(int c) {
  s[n++] = c;
  pos++;
  int last = 0;
  while (pos > 0) {
    go_edge();
    int edge = s[n - pos];
    int &v = to[node][edge];
    int t = s[adla[v] + pos - 1];
    if (v == 0) {
      v = make_node(n - pos, inf);
      link[last] = node;
      last = 0;
    } else if (t == c) {
      link[last] = node;
      return;
    } else {
      int u = make_node(adla[v], pos - 1);
      to[u][c] = make_node(n - 1, inf);
      to[u][t] = v;
      adla[v] += pos - 1;
      len[v] -= pos - 1;
      v = u;
      link[last] = u;
      last = u;
    }
    if (node == 0)
      pos--;
    else
      node = link[node];
  }
}
bool isLeaf(int x) { return to[x].empty(); }
long long nc2(long long a) { return (a * (a + 1)) / 2; }
long long ans = 0;
void dfs(int x, int lenSofar) {
  if (isLeaf(x)) {
    long long delx = a.length() - adla[x] - 1;
    long long lox = lenSofar + 1;
    long long hix = lox + delx - 1;
    if (hix >= lox) {
      ans += (hix - lox + 1) * nc2(subCnt[x]);
    }
    return;
  }
  if (x == 0) {
    for (auto child : to[x]) {
      dfs(child.second, lenSofar);
    }
    return;
  }
  long long lox = lenSofar + 1;
  long long hix = lox + len[x] - 1;
  ans += (hix - lox + 1) * nc2(subCnt[x]);
  for (auto child : to[x]) {
    dfs(child.second, lenSofar + len[x]);
  }
}
long long preDfs(int x) {
  subCnt[x] = 0;
  if (isLeaf(x)) {
    subCnt[x] = 1;
    return 1;
  }
  for (auto child : to[x]) {
    subCnt[x] += preDfs(child.second);
  }
  return subCnt[x];
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  len[0] = inf;
  cin >> a;
  a += '$';
  int N = a.length();
  for (int i = 0; i < a.size(); i++) add_letter(a[i]);
  preDfs(0);
  dfs(0, 0);
  cout << ans << endl;
  return 0;
}