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;
template <typename T>
inline T abs(T a) {
  return ((a < 0) ? -a : a);
}
template <typename T>
inline T sqr(T a) {
  return a * a;
}
const int INF = (int)1E9 + 7;
const long double EPS = 1E-9;
const long double PI = 3.1415926535897932384626433832795;
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];
  }
};
const int NMAX = 200000;
node t[2 * NMAX + 100];
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() {
  sz = 1;
  for (int i = 0; i < n; ++i) tree_extend(i);
}
long long ans = 0;
int cnt[2 * NMAX + 100];
void dfs(int v) {
  cnt[v] = t[v].next.empty() ? 1 : 0;
  for (map<char, int>::iterator it = t[v].next.begin(); it != t[v].next.end();
       it++) {
    dfs(it->second);
    cnt[v] += cnt[it->second];
  }
}
void calc(int v) {
  for (map<char, int>::iterator it = t[v].next.begin(); it != t[v].next.end();
       it++) {
    calc(it->second);
    long long cur = (cnt[it->second] * 1LL * (cnt[it->second] + 1)) >> 1;
    long long curcnt = t[it->second].len();
    ans += cur * curcnt;
  }
}
int main() {
  getline(cin, s);
  s += '$';
  n = int((s).size());
  build_tree();
  dfs(0);
  calc(0);
  cerr << ans << endl;
  cout << ans - int((s).size()) << endl;
  return 0;
}