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;
int dy[] = {1, -1, 0, 0, -1, 1, 1, -1};
int dx[] = {0, 0, 1, -1, 1, -1, 1, -1};
void file() {}
void fast() {
  std::ios_base::sync_with_stdio(0);
  cin.tie(NULL);
}
class SuffixArray {
 public:
  int n, alpha = 128;
  string str;
  vector<int> suff, rnk, lcp;
  SuffixArray(string s) {
    str = s;
    str.push_back('\0');
    n = (int)(str.size());
    suff = rnk = lcp = vector<int>(n);
    build_suffix_array();
    build_LCP_array();
  }
  void build_suffix_array() {
    vector<int> bucket_idx(n), newrnk(n), newsuff(n), prev(n), head(alpha, -1);
    for (int i = 0; i < n; i++) {
      prev[i] = head[str[i]];
      head[str[i]] = i;
    }
    int buc = -1, idx = 0;
    for (int i = 0; i < alpha; i++) {
      if (head[i] == -1) continue;
      bucket_idx[++buc] = idx;
      for (int j = head[i]; ~j; j = prev[j]) suff[idx++] = j, rnk[j] = buc;
    }
    int cur_cmp = 1;
    do {
      auto cmp = [&](int a, int b) {
        return rnk[a] < rnk[b] ||
               rnk[a] == rnk[b] && rnk[a + cur_cmp] < rnk[b + cur_cmp];
      };
      for (int i = 0; i < n; i++) {
        int j = suff[i] - cur_cmp;
        if (j < 0) continue;
        newsuff[bucket_idx[rnk[j]]++] = j;
      }
      for (int i = 1; i < n; i++) {
        suff[i] = newsuff[i];
        bool cmpres = cmp(suff[i - 1], suff[i]);
        newrnk[suff[i]] = newrnk[suff[i - 1]] + cmpres;
        if (cmpres) bucket_idx[newrnk[suff[i]]] = i;
      }
      rnk = newrnk;
      cur_cmp <<= 1;
    } while (rnk[suff[n - 1]] != n - 1);
  }
  void build_LCP_array() {
    int cnt = 0;
    for (int i = 0; i < n - 1; i++) {
      int j = suff[rnk[i] - 1];
      while (str[i + cnt] == str[j + cnt]) cnt++;
      lcp[rnk[i]] = cnt;
      if (cnt) cnt--;
    }
  }
  void print_suffix_array() {
    for (int i = 0; i < n; i++)
      cout << str.substr(suff[i]) << ' ' << lcp[i] << '\n';
  }
};
long long solve(string str) {
  map<string, long long> mp;
  long long ret = 0;
  for (int i = 0; i < (int)(str.size()); i++) {
    for (int j = i; j < (int)(str.size()); j++) {
      mp[str.substr(i, j - i + 1)]++;
    }
  }
  for (auto& it : mp) ret += it.second * (it.second + 1LL) / 2;
  return ret;
}
template <typename T>
struct sparse_table {
  vector<vector<T>> sparseTable;
  vector<T> arr;
  vector<int> LOG2;
  int merge(int a, int b) {
    if (arr[a] < arr[b]) return a;
    return b;
  }
  void build_LOG2() {
    LOG2[0] = -1;
    for (int i = 1; i < (int)(LOG2.size()); i++) LOG2[i] = LOG2[i >> 1] + 1;
  }
  sparse_table(vector<T>& v) {
    arr = v;
    int n = v.size();
    LOG2 = vector<int>(n + 1);
    build_LOG2();
    sparseTable = vector<vector<T>>(LOG2[n] + 1);
    sparseTable[0].resize(n);
    iota(sparseTable[0].begin(), sparseTable[0].end(), 0);
    for (int k = 1, len = 1; k <= LOG2[n]; k++, len <<= 1) {
      sparseTable[k].resize(n);
      for (int i = 0; i + len < n; i++)
        sparseTable[k][i] =
            merge(sparseTable[k - 1][i], sparseTable[k - 1][i + len]);
    }
  }
  T query(int l, int r) {
    int k = LOG2[r - l + 1];
    return merge(sparseTable[k][l], sparseTable[k][r - (1 << k) + 1]);
  }
};
int main() {
  file();
  fast();
  string str;
  cin >> str;
  int n = (int)(str.size());
  SuffixArray sa(str);
  long long ans = n * (n + 1LL) / 2;
  vector<int> v1(sa.lcp.begin() + 1, sa.lcp.end());
  sparse_table<int> sp(v1);
  queue<pair<pair<int, int>, int>> q;
  q.push({{0, n - 1}, 0});
  while (!q.empty()) {
    int l = q.front().first.first, r = q.front().first.second;
    int del = q.front().second;
    q.pop();
    if (l > r) continue;
    int idx = sp.query(l, r);
    if (v1[idx] == del) {
      q.push({{l, idx - 1}, del});
      q.push({{idx + 1, r}, del});
      continue;
    }
    int cnt = v1[idx] - del, s = r - l + 2;
    ans += ((s * (s + 1LL) / 2) * cnt - 1LL * s * cnt);
    del += cnt;
    q.push({{l, idx - 1}, del});
    q.push({{idx + 1, r}, del});
  }
  cout << ans << '\n';
  return 0;
}