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 + 4;
struct node {
  int ptr[26], link, len, cl;
};
struct SAM {
  node t[N];
  int las, siz;
  inline void init() {
    siz = 1;
    las = 0;
    t[0].len = 0;
    t[0].link = -1;
  }
  inline void extend(int c) {
    int cur = siz++, p;
    t[cur].len = t[las].len + 1;
    for (p = las; p != -1 && !t[p].ptr[c]; p = t[p].link) t[p].ptr[c] = cur;
    if (p == -1) {
      t[cur].link = 0;
      las = cur;
      return;
    }
    int q = t[p].ptr[c];
    if (t[p].len + 1 == t[q].len) {
      t[cur].link = q;
      las = cur;
      return;
    }
    int clo = siz++;
    t[clo] = t[q];
    t[clo].len = t[p].len + 1;
    t[clo].cl = 1;
    for (; p != -1 && t[p].ptr[c] == q; p = t[p].link) t[p].ptr[c] = clo;
    t[q].link = t[cur].link = clo;
    las = cur;
  }
} sam1, sam2;
int n, tim, siz[N], fa[N], son[N], dep[N], dfn[N], top[N];
int ed[N], ton[N], c[N];
long long ans, d[N];
vector<int> e[N];
char S[N];
struct int_cmp {
  bool operator()(int x, int y) const { return dfn[x] < dfn[y]; }
};
set<int, int_cmp> s[N];
void dfs_1(int x) {
  siz[x] = 1;
  dep[x] = dep[fa[x]] + 1;
  for (auto v : e[x]) {
    fa[v] = x;
    dfs_1(v);
    siz[x] += siz[v];
    if (siz[v] > siz[son[x]]) son[x] = v;
  }
}
void dfs_2(int x, int tp) {
  top[x] = tp;
  dfn[x] = ++tim;
  if (son[x]) dfs_2(son[x], tp);
  for (auto v : e[x])
    if (v != fa[x] && v != son[x]) dfs_2(v, v);
}
inline int lca(int u, int v) {
  while (top[u] != top[v]) {
    if (dep[top[u]] < dep[top[v]]) u ^= v ^= u ^= v;
    u = fa[top[u]];
  }
  return dep[u] < dep[v] ? u : v;
}
inline int distan(int u, int v) {
  return sam2.t[u].len - sam2.t[lca(u, v)].len;
}
inline void insert(int x, int v) {
  auto it = s[x].upper_bound(v);
  auto it2 = it;
  if (it != s[x].begin()) it2--;
  if (it != s[x].end()) {
    if (it != s[x].begin()) {
      d[x] -= distan(*it, *it2);
    } else {
      d[x] -= sam2.t[*it].len + 1;
    }
  }
  if (it != s[x].begin()) {
    d[x] += distan(v, *it2);
  } else {
    d[x] += sam2.t[v].len + 1;
  }
  if (it != s[x].end()) {
    d[x] += distan(*it, v);
  }
  s[x].insert(v);
}
int main() {
  scanf("%s", S + 1);
  n = strlen(S + 1);
  sam1.init();
  sam2.init();
  for (int i = n; i; i--) {
    sam2.extend(S[i] - 'a');
    ed[i] = sam2.las;
  }
  for (int i = 1; i < sam2.siz; i++) e[sam2.t[i].link].push_back(i);
  dfs_1(0);
  dfs_2(0, 0);
  for (int i = 1; i <= n; i++) {
    sam1.extend(S[i] - 'a');
    if (i < n) insert(sam1.las, ed[i + 2]);
  }
  for (int i = 1; i < sam1.siz; i++) ton[sam1.t[i].len]++;
  for (int i = 1; i <= n; i++) ton[i] += ton[i - 1];
  for (int i = 1; i < sam1.siz; i++) c[ton[sam1.t[i].len]--] = i;
  insert(0, ed[2]);
  for (int i = sam1.siz - 1, u; i >= 0; i--) {
    u = c[i];
    if (!i) {
      ans += d[u];
      break;
    }
    ans += (d[u] + 1) * (sam1.t[u].len - sam1.t[sam1.t[u].link].len);
    if (s[u].size() > s[sam1.t[u].link].size()) {
      swap(s[u], s[sam1.t[u].link]);
      swap(d[u], d[sam1.t[u].link]);
    }
    for (auto v : s[u]) insert(sam1.t[u].link, v);
  }
  cout << ans + 1 << "\n";
  return (0 - 0);
}