#include <bits/stdc++.h>
template <typename T>
inline void read(T &x) {
  x = 0;
  char c = getchar();
  bool flag = false;
  while (!isdigit(c)) {
    if (c == '-') flag = true;
    c = getchar();
  }
  while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
  if (flag) x = -x;
}
using namespace std;
int n;
char s[201000];
int son[201000][26], fa[201000], len[201000], tot = 1, lst = 1;
inline void clear() {
  memset(son, 0, sizeof(son));
  memset(fa, 0, sizeof(fa));
  memset(len, 0, sizeof(len));
  tot = lst = 1;
}
inline void ins(int c) {
  int np = ++tot, p = lst;
  lst = np;
  len[np] = len[p] + 1;
  while (p && !son[p][c]) son[p][c] = np, p = fa[p];
  if (!p) return fa[np] = 1, void();
  int q = son[p][c];
  if (len[q] == len[p] + 1) return fa[np] = q, void();
  int nq = ++tot;
  len[nq] = len[p] + 1;
  fa[nq] = fa[q], fa[q] = fa[np] = nq;
  memcpy(son[nq], son[q], sizeof(son[q]));
  while (p && son[p][c] == q) son[p][c] = nq, p = fa[p];
}
int pos[201000];
struct edge {
  int nxt, to;
  edge() {}
  edge(int jzp, int zzz) { nxt = jzp, to = zzz; }
} e[201000 << 1];
int head[201000], ecnt;
inline void addedge(int from, int to) {
  e[++ecnt] = edge(head[from], to);
  head[from] = ecnt;
}
int dep[201000], dis[201000], ldfn[201000], rdfn[201000], dedfn[201000 << 1],
    dfn[201000], dcnt, lrdcnt;
void dfs_dfn(int cur) {
  ldfn[cur] = rdfn[cur] = ++lrdcnt;
  dedfn[lrdcnt] = cur;
  dfn[cur] = ++dcnt;
  dep[cur] = dep[fa[cur]] + 1;
  for (int i = head[cur]; i; i = e[i].nxt) {
    int to = e[i].to;
    dfs_dfn(to);
    rdfn[cur] = ++lrdcnt;
    dedfn[lrdcnt] = cur;
  }
}
inline int get_min(int x, int y) { return dep[x] < dep[y] ? x : y; }
int st[20][201000 << 1], Lg2[201000 << 1];
inline void build_st() {
  for (int i = 0; i < lrdcnt; ++i) st[0][i] = dedfn[i];
  Lg2[0] = -1;
  for (int i = 1; i <= lrdcnt; ++i) Lg2[i] = Lg2[i >> 1] + 1;
  for (int j = 1; j <= Lg2[lrdcnt]; ++j)
    for (int i = 1; i + (1 << j) - 1 <= lrdcnt; ++i)
      st[j][i] = get_min(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
}
inline int get_lca(int x, int y) {
  int l = min(ldfn[x], ldfn[y]), r = max(rdfn[x], rdfn[y]);
  int j = Lg2[r - l + 1];
  return get_min(st[j][l], st[j][r - (1 << j) + 1]);
}
namespace SGT {
int ls[5001000], rs[5001000], lft[5001000], rgt[5001000];
long long sum[5001000];
int ttot, rt[201000];
inline void pushup(int cur) {
  if (!ls[cur])
    lft[cur] = lft[rs[cur]], rgt[cur] = rgt[rs[cur]], sum[cur] = sum[rs[cur]];
  else if (!rs[cur])
    lft[cur] = lft[ls[cur]], rgt[cur] = rgt[ls[cur]], sum[cur] = sum[ls[cur]];
  else {
    lft[cur] = lft[ls[cur]], rgt[cur] = rgt[rs[cur]];
    sum[cur] =
        sum[ls[cur]] + sum[rs[cur]] - dis[get_lca(rgt[ls[cur]], lft[rs[cur]])];
  }
}
void ins(int L, int R, int pos, int nd, int &cur) {
  if (!cur) cur = ++ttot;
  if (L == R) return lft[cur] = rgt[cur] = nd, sum[cur] = dis[nd], void();
  int mid = (L + R) >> 1;
  if (pos <= mid)
    ins(L, mid, pos, nd, ls[cur]);
  else
    ins(mid + 1, R, pos, nd, rs[cur]);
  pushup(cur);
}
inline void ins(int p, int cur) {
  if (p < 1 || p > n) return;
  p = pos[p];
  ins(1, dcnt, dfn[p], p, rt[cur]);
}
int merge(int L, int R, int x, int y) {
  if (!x || !y) return x ^ y;
  if (L == R) return puts("QAQ"), x;
  int mid = (L + R) >> 1;
  ls[x] = merge(L, mid, ls[x], ls[y]);
  rs[x] = merge(mid + 1, R, rs[x], rs[y]);
  pushup(x);
  return x;
}
inline void merge(int x, int y) { rt[x] = merge(1, dcnt, rt[x], rt[y]); }
inline long long query(int x) { return sum[rt[x]]; }
}  // namespace SGT
long long ans = 2;
void dfs_ans(int cur) {
  for (int i = head[cur]; i; i = e[i].nxt) {
    int to = e[i].to;
    dfs_ans(to);
    SGT::merge(cur, to);
  }
  ans += 1ll * (len[cur] - len[fa[cur]]) * SGT::query(cur);
}
int main() {
  scanf("%s", s + 1);
  n = strlen(s + 1);
  for (int i = 1; i <= n; ++i) {
    ins(s[i] - 'a'),
        pos[i] = lst,
        ans += len[lst] - len[fa[lst]] + (i == n ? 0 : len[lst] - len[fa[lst]]);
  }
  memcpy(dis, len, sizeof(len));
  for (int i = 2; i <= tot; ++i) addedge(fa[i], i);
  dfs_dfn(1);
  build_st();
  memset(head, 0, sizeof(head));
  ecnt = 1;
  clear();
  reverse(s + 1, s + 1 + n);
  for (int i = 1; i <= n; ++i)
    ins(s[i] - 'a'), ans += (i == n ? 0 : len[lst] - len[fa[lst]]),
        SGT::ins(n - (len[lst] + 2) + 1, lst);
  for (int i = 2; i <= tot; ++i) addedge(fa[i], i);
  dfs_ans(1);
  printf("%lld\n", ans);
  return 0;
}

### Prompt

Develop a solution in CPP to the problem described below:

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.

### Response

```cpp
#include <bits/stdc++.h>
template <typename T>
inline void read(T &x) {
  x = 0;
  char c = getchar();
  bool flag = false;
  while (!isdigit(c)) {
    if (c == '-') flag = true;
    c = getchar();
  }
  while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
  if (flag) x = -x;
}
using namespace std;
int n;
char s[201000];
int son[201000][26], fa[201000], len[201000], tot = 1, lst = 1;
inline void clear() {
  memset(son, 0, sizeof(son));
  memset(fa, 0, sizeof(fa));
  memset(len, 0, sizeof(len));
  tot = lst = 1;
}
inline void ins(int c) {
  int np = ++tot, p = lst;
  lst = np;
  len[np] = len[p] + 1;
  while (p && !son[p][c]) son[p][c] = np, p = fa[p];
  if (!p) return fa[np] = 1, void();
  int q = son[p][c];
  if (len[q] == len[p] + 1) return fa[np] = q, void();
  int nq = ++tot;
  len[nq] = len[p] + 1;
  fa[nq] = fa[q], fa[q] = fa[np] = nq;
  memcpy(son[nq], son[q], sizeof(son[q]));
  while (p && son[p][c] == q) son[p][c] = nq, p = fa[p];
}
int pos[201000];
struct edge {
  int nxt, to;
  edge() {}
  edge(int jzp, int zzz) { nxt = jzp, to = zzz; }
} e[201000 << 1];
int head[201000], ecnt;
inline void addedge(int from, int to) {
  e[++ecnt] = edge(head[from], to);
  head[from] = ecnt;
}
int dep[201000], dis[201000], ldfn[201000], rdfn[201000], dedfn[201000 << 1],
    dfn[201000], dcnt, lrdcnt;
void dfs_dfn(int cur) {
  ldfn[cur] = rdfn[cur] = ++lrdcnt;
  dedfn[lrdcnt] = cur;
  dfn[cur] = ++dcnt;
  dep[cur] = dep[fa[cur]] + 1;
  for (int i = head[cur]; i; i = e[i].nxt) {
    int to = e[i].to;
    dfs_dfn(to);
    rdfn[cur] = ++lrdcnt;
    dedfn[lrdcnt] = cur;
  }
}
inline int get_min(int x, int y) { return dep[x] < dep[y] ? x : y; }
int st[20][201000 << 1], Lg2[201000 << 1];
inline void build_st() {
  for (int i = 0; i < lrdcnt; ++i) st[0][i] = dedfn[i];
  Lg2[0] = -1;
  for (int i = 1; i <= lrdcnt; ++i) Lg2[i] = Lg2[i >> 1] + 1;
  for (int j = 1; j <= Lg2[lrdcnt]; ++j)
    for (int i = 1; i + (1 << j) - 1 <= lrdcnt; ++i)
      st[j][i] = get_min(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
}
inline int get_lca(int x, int y) {
  int l = min(ldfn[x], ldfn[y]), r = max(rdfn[x], rdfn[y]);
  int j = Lg2[r - l + 1];
  return get_min(st[j][l], st[j][r - (1 << j) + 1]);
}
namespace SGT {
int ls[5001000], rs[5001000], lft[5001000], rgt[5001000];
long long sum[5001000];
int ttot, rt[201000];
inline void pushup(int cur) {
  if (!ls[cur])
    lft[cur] = lft[rs[cur]], rgt[cur] = rgt[rs[cur]], sum[cur] = sum[rs[cur]];
  else if (!rs[cur])
    lft[cur] = lft[ls[cur]], rgt[cur] = rgt[ls[cur]], sum[cur] = sum[ls[cur]];
  else {
    lft[cur] = lft[ls[cur]], rgt[cur] = rgt[rs[cur]];
    sum[cur] =
        sum[ls[cur]] + sum[rs[cur]] - dis[get_lca(rgt[ls[cur]], lft[rs[cur]])];
  }
}
void ins(int L, int R, int pos, int nd, int &cur) {
  if (!cur) cur = ++ttot;
  if (L == R) return lft[cur] = rgt[cur] = nd, sum[cur] = dis[nd], void();
  int mid = (L + R) >> 1;
  if (pos <= mid)
    ins(L, mid, pos, nd, ls[cur]);
  else
    ins(mid + 1, R, pos, nd, rs[cur]);
  pushup(cur);
}
inline void ins(int p, int cur) {
  if (p < 1 || p > n) return;
  p = pos[p];
  ins(1, dcnt, dfn[p], p, rt[cur]);
}
int merge(int L, int R, int x, int y) {
  if (!x || !y) return x ^ y;
  if (L == R) return puts("QAQ"), x;
  int mid = (L + R) >> 1;
  ls[x] = merge(L, mid, ls[x], ls[y]);
  rs[x] = merge(mid + 1, R, rs[x], rs[y]);
  pushup(x);
  return x;
}
inline void merge(int x, int y) { rt[x] = merge(1, dcnt, rt[x], rt[y]); }
inline long long query(int x) { return sum[rt[x]]; }
}  // namespace SGT
long long ans = 2;
void dfs_ans(int cur) {
  for (int i = head[cur]; i; i = e[i].nxt) {
    int to = e[i].to;
    dfs_ans(to);
    SGT::merge(cur, to);
  }
  ans += 1ll * (len[cur] - len[fa[cur]]) * SGT::query(cur);
}
int main() {
  scanf("%s", s + 1);
  n = strlen(s + 1);
  for (int i = 1; i <= n; ++i) {
    ins(s[i] - 'a'),
        pos[i] = lst,
        ans += len[lst] - len[fa[lst]] + (i == n ? 0 : len[lst] - len[fa[lst]]);
  }
  memcpy(dis, len, sizeof(len));
  for (int i = 2; i <= tot; ++i) addedge(fa[i], i);
  dfs_dfn(1);
  build_st();
  memset(head, 0, sizeof(head));
  ecnt = 1;
  clear();
  reverse(s + 1, s + 1 + n);
  for (int i = 1; i <= n; ++i)
    ins(s[i] - 'a'), ans += (i == n ? 0 : len[lst] - len[fa[lst]]),
        SGT::ins(n - (len[lst] + 2) + 1, lst);
  for (int i = 2; i <= tot; ++i) addedge(fa[i], i);
  dfs_ans(1);
  printf("%lld\n", ans);
  return 0;
}

```