Problem: Consider a string s of n lowercase English letters. Let t_i be the string obtained by replacing the i-th character of s with an asterisk character *. For example, when s = abc, we have t_1 = \tt{*bc}, t_2 = \tt{a*c}, and t_3 = \tt{ab*}.

Given a string s, count the number of distinct strings of lowercase English letters and asterisks that occur as a substring of at least one string in the set \\{s, t_1, …, t_n \}. The empty string should be counted.

Note that *'s are just characters and do not play any special role as in, for example, regex matching.

Input

The only line contains a string s of n lowercase English letters (1 ≤ n ≤ 10^5).

Output

Print a single integer — the number of distinct strings of s, t_1, …, t_n.

Example

Input


abc


Output


15

Note

For the sample case, the distinct substrings are (empty string), a, b, c, *, ab, a*, bc, b*, *b, *c, abc, ab*, a*c, *bc.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 1;
inline int min(const int& x, const int& y) { return (x - y >> 31) ? x : y; }
namespace ST {
int lg[N], t[20][N];
inline void build(int* a, int n) {
  copy(a + 1, a + 1 + n, t[0] + 1);
  for (int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;
  for (int i = 1; i <= 19; i++)
    for (int j = 1; j <= n - (1 << i); j++)
      t[i][j] = min(t[i - 1][j], t[i - 1][j + (1 << i - 1)]);
}
inline int ask(int l, int r) {
  assert(l <= r);
  int p = lg[r - l];
  return min(t[p][l], t[p][r - (1 << p)]);
}
}  // namespace ST
namespace SA {
int n, m, sa[N], x[N], y[N], c[N], h[N];
char* st;
inline void input(char* a, int len) {
  n = len, m = 128, st = a;
  for (int i = 1; i <= n; i++) x[i] = st[i], sa[i] = i;
}
inline void radix_sort() {
  for (int i = 1; i <= m; i++) c[i] = 0;
  for (int i = 1; i <= n; i++) c[x[i]]++;
  for (int i = 1; i <= m; i++) c[i] += c[i - 1];
  for (int i = n; i >= 1; i--) sa[c[x[y[i]]]--] = y[i];
}
inline void init() {
  for (int k = 0, p = 0; k <= n; k = k << 1 | !k) {
    for (int i = n - k + 1; i <= n; i++) y[++p] = i;
    for (int i = 1; i <= n; i++)
      if (sa[i] > k) y[++p] = sa[i] - k;
    radix_sort(), swap(x, y), p = 0;
    for (int i = 1; i <= n; i++)
      x[sa[i]] = p +=
          y[sa[i]] != y[sa[i - 1]] || y[sa[i] + k] != y[sa[i - 1] + k];
    if (p >= n) break;
    m = p, p = 0;
  }
  for (int i = 1; i <= n; i++) {
    int& p = h[x[i]] = max(0, h[x[i - 1]] - 1);
    while (st[i + p] == st[sa[x[i] + 1] + p]) h[x[i]]++;
  }
  ST::build(h, n);
}
}  // namespace SA
struct tree {
  set<int> mp;
  long long int val;
  inline void init() { mp.clear(), mp.insert(0), mp.insert(N), val = 0; }
  inline int pre(int x) { return *--mp.lower_bound(x); }
  inline int nxt(int x) { return *mp.upper_bound(x); }
  inline void add(int x, int y, int w) {
    if (x && y != N) val += ST::ask(x, y) * w;
  }
  inline void ins(int x) {
    int p = pre(x), q = nxt(x);
    add(p, q, 1), add(p, x, -1), add(x, q, -1), mp.insert(x);
  }
} t[N];
namespace SAM {
int n, tot, last, top;
int fa[N], len[N], ch[N][26], d[N], sta[N], pos[N];
inline void cpy(int x, int y) {
  for (int i = 0; i <= 25; i++) ch[x][i] = ch[y][i];
}
inline void ins(int x) {
  int p(last), np, q, nq;
  len[np = last = ++tot] = len[p] + 1;
  while (p && !ch[p][x]) ch[p][x] = np, p = fa[p];
  if (!p) return void(fa[np] = 1);
  if (len[q = ch[p][x]] == len[p] + 1) return void(fa[np] = q);
  cpy(nq = ++tot, q), len[nq] = len[p] + 1, fa[nq] = fa[q], fa[q] = fa[np] = nq;
  while (p && ch[p][x] == q) ch[p][x] = nq, p = fa[p];
}
inline void input(char* a, int len) {
  n = len, tot = last = pos[0] = 1;
  for (int i = 1; i <= n; i++) ins(a[i] - 'a'), pos[i] = last;
}
inline void merge(tree& x, tree& y) {
  if (x.mp.size() < y.mp.size()) swap(x, y);
  for (int v : y.mp)
    if (v && v != N) x.ins(v), x.val += n - SA::sa[v] + 1;
}
inline void work() {
  long long int ans = 0;
  for (int i = 0; i <= tot; i++) d[fa[i]]++, t[i].init();
  for (int i = 1; i <= tot; i++)
    if (!d[i]) sta[++top] = i;
  for (int i = 0; i <= n - 2; i++)
    t[pos[i]].ins(SA::x[i + 2]), t[pos[i]].val += n - i - 1;
  for (int i = 1; i <= tot; i++) ans += len[i] - len[fa[i]] << (i != pos[n]);
  for (int u; u = sta[top--];) {
    ans += t[u].val * (len[u] - len[fa[u]]);
    if (fa[u]) merge(t[fa[u]], t[u]);
    if (!--d[fa[u]]) sta[++top] = fa[u];
  }
  cout << ans + t[1].val + 2;
}
};  // namespace SAM
int n;
char a[N];
inline void input() { scanf("%s", a + 1), n = strlen(a + 1), SA::input(a, n); }
inline void init() { SA::init(), SAM::input(a, n); }
inline void work() { SAM::work(); }
int main() {
  input();
  init();
  work();
  return 0;
}