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 GCC optimaze("Ofast");
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native")
#pragma GCC optimize("unroll-loops")
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct suff_arr {
  vector<int> p, c, np, nc, h, lcp, p2;
  string s;
  int n;
  suff_arr(string &s) {
    this->s = s + char(0);
    this->n = this->s.size();
  }
  int mode1(int a, int k, int n) { return (a + (1 << k)) % n; }
  int mode2(int a, int k, int n) { return (a - (1 << k) + n) % n; }
  bool prov(int i, int j, int k) {
    return c[i] != c[j] || c[mode1(i, (k - 1), n)] != c[mode1(j, (k - 1), n)];
  }
  void build() {
    p.resize(n);
    c = np = nc = h = p;
    vector<pair<char, int>> in;
    for (int i = 0; i < s.size(); i++) in.push_back({s[i], i});
    sort(in.begin(), in.end());
    p[0] = in[0].second;
    int g = c[p[0]] = h[0] = 0, k = 1;
    for (int i = 1; i < n; i++) {
      p[i] = in[i].second;
      if (in[i - 1].first != in[i].first) g++, h[g] = i;
      c[p[i]] = g;
    }
    while (1 << (k - 1) < n) {
      for (int i = 0; i < n; i++) {
        int v = mode2(p[i], (k - 1), n);
        np[h[c[v]]++] = v;
      }
      nc[np[0]] = h[0] = g = 0;
      for (int i = 1; i < n; i++) {
        if (prov(np[i - 1], np[i], k)) g++, h[g] = i;
        nc[np[i]] = g;
      }
      c = nc, p = np, k++;
      if (g == n) break;
    }
  }
  void build_lcp() {
    lcp.resize(n);
    p2.resize(n);
    for (int i = 0; i < n; i++) p2[p[i]] = i;
    for (int i = 0; i < n; i++) {
      if (i > 0) lcp[p2[i]] = max(lcp[p2[i - 1]] - 1, 0);
      while (p2[i] + 1 < n && s[i + lcp[p2[i]]] == s[p[p2[i] + 1] + lcp[p2[i]]])
        lcp[p2[i]]++;
    }
  }
};
signed main() {
  srand(1);
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.setf(ios::fixed);
  cout.precision(10);
  string s;
  cin >> s;
  suff_arr ms(s);
  ms.build();
  ms.build_lcp();
  int n = s.size();
  stack<pair<int, pair<int, long long>>> tu;
  long long ans = 1LL * n * (n + 1) / 2;
  for (int i = 0; i < ms.n; i++) {
    int x = ms.lcp[i];
    while (tu.size() && tu.top().first > x) tu.pop();
    if (tu.size()) {
      long long sum = 0;
      sum += tu.top().second.second;
      sum += 1LL * (i - tu.top().second.first) * x;
      tu.push({x, {i, sum}});
      ans += sum;
    } else
      tu.push({x, {i, 0}});
  }
  cout << ans;
}