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>
#pragma comment(linker, "/STACK:200000000")
using namespace std;
const int INF = (int)1E9;
const long long INF64 = (long long)1E18;
const double EPS = 1E-9;
const double PI = acos((double)0) * 2;
const int MAXN = 210 * 1000;
string s;
int n;
struct node {
  int l, r, par, link;
  map<char, int> next;
  node(int l = 0, int r = 0, int par = -1) : l(l), r(r), par(par), link(-1) {}
  int len() { return r - l; }
  int &get(char c) {
    if (!next.count(c)) next[c] = -1;
    return next[c];
  }
};
node t[MAXN];
int sz;
struct state {
  int v, pos;
  state(int v, int pos) : v(v), pos(pos) {}
};
state ptr(0, 0);
state go(state st, int l, int r) {
  while (l < r)
    if (st.pos == t[st.v].len()) {
      st = state(t[st.v].get(s[l]), 0);
      if (st.v == -1) return st;
    } else {
      if (s[t[st.v].l + st.pos] != s[l]) return state(-1, -1);
      if (r - l < t[st.v].len() - st.pos) return state(st.v, st.pos + r - l);
      l += t[st.v].len() - st.pos;
      st.pos = t[st.v].len();
    }
  return st;
}
int split(state st) {
  if (st.pos == t[st.v].len()) return st.v;
  if (st.pos == 0) return t[st.v].par;
  node v = t[st.v];
  int id = sz++;
  t[id] = node(v.l, v.l + st.pos, v.par);
  t[v.par].get(s[v.l]) = id;
  t[id].get(s[v.l + st.pos]) = st.v;
  t[st.v].par = id;
  t[st.v].l += st.pos;
  return id;
}
int get_link(int v) {
  if (t[v].link != -1) return t[v].link;
  if (t[v].par == -1) return 0;
  int to = get_link(t[v].par);
  return t[v].link = split(
             go(state(to, t[to].len()), t[v].l + (t[v].par == 0), t[v].r));
}
void tree_extend(int pos) {
  for (;;) {
    state nptr = go(ptr, pos, pos + 1);
    if (nptr.v != -1) {
      ptr = nptr;
      return;
    }
    int mid = split(ptr);
    int leaf = sz++;
    t[leaf] = node(pos, n, mid);
    t[mid].get(s[pos]) = leaf;
    ptr.v = get_link(mid);
    ptr.pos = t[ptr.v].len();
    if (!mid) break;
  }
}
void build_tree() {
  t[0] = node();
  sz = 1;
  for (int i = 0; i < n; ++i) tree_extend(i);
}
bool read() {
  char buf[MAXN];
  if (scanf(" %s", buf) == 1) {
    s = buf;
    s += '$';
    n = (int)s.length();
    return true;
  }
  return false;
}
long long ans;
int dfs(int v) {
  int leaves = 0;
  for (map<char, int>::iterator it = t[v].next.begin(); it != t[v].next.end();
       ++it) {
    int to = it->second;
    leaves += dfs(to);
  }
  if (leaves == 0) ++leaves;
  int len = t[v].r - t[v].l;
  ans += len * 1ll * leaves * (leaves + 1) / 2;
  return leaves;
}
void solve() {
  build_tree();
  ans = 0;
  dfs(0);
  ans -= n;
  cout << ans << endl;
}
int main() {
  if (!read()) throw;
  solve();
}