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;
using LL = long long;
const int MAX_N = 2e5 + 5;
char str[MAX_N];
int N;
struct SAM {
  int ch[MAX_N][26], len[MAX_N], fa[MAX_N], Pos[MAX_N];
  int tot, lst;
  SAM() { tot = lst = 1; }
  void extend(int c) {
    int p = lst, np = ++tot;
    len[np] = len[p] + 1;
    while (p && !ch[p][c]) ch[p][c] = np, p = fa[p];
    if (!p)
      fa[np] = 1;
    else {
      int q = ch[p][c];
      if (len[q] == len[p] + 1)
        fa[np] = q;
      else {
        int nq = ++tot;
        len[nq] = len[p] + 1, fa[nq] = fa[q], fa[q] = fa[np] = nq;
        for (int i = 0; i < 26; i++) ch[nq][i] = ch[q][i];
        while (p && ch[p][c] == q) ch[p][c] = nq, p = fa[p];
      }
    }
    lst = np;
  }
  void clear() {
    for (int i = 1; i <= tot; i++) {
      fa[i] = len[i] = 0;
      for (int j = 0; j < 26; j++) ch[i][j] = 0;
    }
    lst = tot = 1;
  }
} S, T;
LL ans = 2;
vector<int> G[MAX_N], E[MAX_N];
int fa[MAX_N], dep[MAX_N], top[MAX_N], son[MAX_N], siz[MAX_N];
int L[MAX_N], dfn[MAX_N], tim;
void dfs1(int x) {
  dep[x] = dep[fa[x]] + 1, siz[x] = 1;
  for (int v : G[x]) {
    if (v == fa[x]) continue;
    fa[v] = x, dfs1(v), siz[x] += siz[v];
    if (siz[v] > siz[son[x]]) son[x] = v;
  }
}
void dfs2(int x, int tp) {
  dfn[L[x] = ++tim] = x, top[x] = tp;
  if (son[x]) dfs2(son[x], tp);
  for (int v : G[x]) {
    if (v == son[x] || v == fa[x]) continue;
    dfs2(v, v);
  }
}
int LCA(int x, int y) {
  while (top[x] != top[y]) {
    if (dep[top[x]] < dep[top[y]]) swap(x, y);
    x = fa[top[x]];
  }
  return dep[x] < dep[y] ? x : y;
}
int ls[MAX_N << 5], rs[MAX_N << 5], vl[MAX_N << 5], vr[MAX_N << 5];
int rt[MAX_N], tot;
LL sum[MAX_N << 5];
void pushup(int o) {
  sum[o] = sum[ls[o]] + sum[rs[o]] -
           (ls[o] && rs[o] ? T.len[LCA(vr[ls[o]], vl[rs[o]])] : 0);
  vl[o] = ls[o] ? vl[ls[o]] : vl[rs[o]];
  vr[o] = rs[o] ? vr[rs[o]] : vr[ls[o]];
}
void modify(int &o, int pos, int l = 1, int r = tim) {
  if (!o) o = ++tot;
  if (l == r) return (void)(sum[o] = T.len[dfn[pos]], vl[o] = vr[o] = dfn[pos]);
  int mid = (l + r) >> 1;
  if (pos <= mid)
    modify(ls[o], pos, l, mid);
  else
    modify(rs[o], pos, mid + 1, r);
  pushup(o);
}
int merge(int x, int y) {
  if (!x || !y) return x + y;
  if (!ls[x] && !rs[x]) return x;
  ls[x] = merge(ls[x], ls[y]);
  rs[x] = merge(rs[x], rs[y]);
  return pushup(x), x;
}
void dfs(int x) {
  for (int v : E[x]) dfs(v), rt[x] = merge(rt[x], rt[v]);
  ans += 1ll * (S.len[x] - S.len[S.fa[x]]) * sum[rt[x]];
}
int main() {
  scanf("%s", str + 1);
  N = strlen(str + 1);
  for (int i = N; i; i--) T.extend(str[i] - 'a'), T.Pos[i] = T.lst;
  for (int i = 2; i <= N; i++) S.extend(str[i] - 'a');
  for (int i = 1; i <= S.tot; i++) ans += S.len[i] - S.len[S.fa[i]];
  S.clear();
  for (int i = 1; i < N; i++) S.extend(str[i] - 'a'), S.Pos[i] = S.lst;
  for (int i = 1; i <= S.tot; i++) ans += S.len[i] - S.len[S.fa[i]];
  S.extend(str[N] - 'a'), S.Pos[N] = S.lst;
  for (int i = 1; i <= S.tot; i++) ans += S.len[i] - S.len[S.fa[i]];
  for (int i = 2; i <= T.tot; i++) G[T.fa[i]].push_back(i);
  for (int i = 2; i <= S.tot; i++) E[S.fa[i]].push_back(i);
  dfs1(1), dfs2(1, 1);
  for (int i = 1; i <= N - 2; i++) modify(rt[S.Pos[i]], L[T.Pos[i + 2]]);
  dfs(1);
  printf("%lld\n", ans);
  return 0;
}