#include <bits/stdc++.h>
using namespace std;
inline void read(int &x) {
  int v = 0, f = 1;
  char c = getchar();
  while (!isdigit(c) && c != '-') c = getchar();
  if (c == '-')
    f = -1;
  else
    v = (c & 15);
  while (isdigit(c = getchar())) v = (v << 1) + (v << 3) + (c & 15);
  x = v * f;
}
inline void read(long long &x) {
  long long v = 0ll, f = 1ll;
  char c = getchar();
  while (!isdigit(c) && c != '-') c = getchar();
  if (c == '-')
    f = -1;
  else
    v = (c & 15);
  while (isdigit(c = getchar())) v = (v << 1) + (v << 3) + (c & 15);
  x = v * f;
}
inline void readc(char &x) {
  char c;
  while (((c = getchar()) == ' ') || c == '\n')
    ;
  x = c;
}
int n, m, i, j;
long long ans;
string st;
struct sam {
  int fa[200005], l[200005], ch[200005][26], cnt, lst, ed[200005], mp[200005];
  void init() { cnt = lst = 1; }
  void ins(char c, int i) {
    int np = ++cnt, p = lst;
    lst = np;
    l[np] = l[p] + 1;
    ed[np] = i;
    mp[i] = np;
    for (; p && !ch[p][c - 'a']; p = fa[p]) ch[p][c - 'a'] = np;
    if (!p) {
      fa[np] = 1;
      return;
    }
    int q = ch[p][c - 'a'];
    if (l[p] + 1 == l[q]) {
      fa[np] = q;
      return;
    }
    int nq = ++cnt;
    l[nq] = l[p] + 1;
    fa[nq] = fa[q];
    fa[q] = fa[np] = nq;
    memcpy(ch[nq], ch[q], sizeof(ch[q]));
    for (; p && ch[p][c - 'a'] == q; p = fa[p]) ch[p][c - 'a'] = nq;
  }
  long long count() {
    long long s = 0;
    int i;
    for ((i) = (2); (i) <= (cnt); (i)++) {
      s += l[i] - l[fa[i]];
    }
    return s;
  }
} s1, s2;
int dep[200005], fa[200005][19];
vector<int> e1[200005], e2[200005];
int ti, dfn[200005], mp[200005];
void dfs1(int x) {
  mp[dfn[x] = ++ti] = x;
  for (__typeof((e2[x]).begin()) it = (e2[x]).begin(); it != (e2[x]).end();
       it++) {
    fa[*it][0] = x;
    dep[*it] = dep[x] + 1;
    dfs1(*it);
  }
}
int lca(int x, int y) {
  if (dep[x] < dep[y]) swap(x, y);
  int t = dep[x] - dep[y], i;
  for ((i) = (18); (i) >= (0); (i)--)
    if ((t >> i) & 1) x = fa[x][i];
  if (x == y) return x;
  for ((i) = (18); (i) >= (0); (i)--)
    if (fa[x][i] != fa[y][i]) {
      x = fa[x][i];
      y = fa[y][i];
    }
  return fa[x][0];
}
int dis(int x, int y) { return s2.l[x] + s2.l[y] - 2 * s2.l[lca(x, y)]; }
int rt[200005];
int lc[4000005], rc[4000005], cnt;
struct nd {
  int l, r;
  long long res;
} tr[4000005];
nd merge(nd x, nd y) {
  nd z;
  z.l = x.l;
  z.r = y.r;
  z.res = x.res + y.res + dis(x.r, y.l);
  return z;
}
void pushup(int x) {
  if (!lc[x])
    tr[x] = tr[rc[x]];
  else if (!rc[x])
    tr[x] = tr[lc[x]];
  else
    tr[x] = merge(tr[lc[x]], tr[rc[x]]);
}
void update(int &x, int l, int r, int y) {
  if (!x) x = ++cnt;
  if (l == r) {
    tr[x] = (nd){mp[y], mp[y], 0};
    return;
  }
  int mid = (l + r) / 2;
  if (y <= mid)
    update(lc[x], l, mid, y);
  else
    update(rc[x], mid + 1, r, y);
  pushup(x);
}
void merge(int &x, int y) {
  if (!x || !y) {
    x = x + y;
    return;
  }
  merge(lc[x], lc[y]);
  merge(rc[x], rc[y]);
  pushup(x);
}
void dfs2(int x) {
  if (s1.ed[x] && s1.ed[x] <= n - 2) {
    update(rt[x], 1, ti, dfn[s2.mp[s1.ed[x] + 2]]);
  }
  for (__typeof((e1[x]).begin()) it = (e1[x]).begin(); it != (e1[x]).end();
       it++) {
    dfs2(*it);
    merge(rt[x], rt[*it]);
  }
  ans += 1ll * (s1.l[x] - s1.l[s1.fa[x]]) *
         (tr[rt[x]].res + dis(tr[rt[x]].l, 1) + dis(1, tr[rt[x]].r)) / 2;
}
int main() {
  ios_base::sync_with_stdio(false);
  ;
  cin >> st;
  n = st.size();
  st = " " + st;
  ans = 2;
  s1.init();
  s2.init();
  for (((i)) = (1); ((i)) <= ((n - 1)); ((i))++) s1.ins(st[i], i);
  ans += s1.count();
  s1.ins(st[n], n);
  ans += s1.count();
  for (((i)) = (1); ((i)) <= ((n - 1)); ((i))++)
    s2.ins(st[n - i + 1], n - i + 1);
  ans += s2.count();
  s2.ins(st[1], 1);
  for ((i) = (2); (i) <= (s1.cnt); (i)++) e1[s1.fa[i]].push_back(i);
  for ((i) = (2); (i) <= (s2.cnt); (i)++) e2[s2.fa[i]].push_back(i);
  dfs1(1);
  for (((j)) = (1); ((j)) <= ((18)); ((j))++)
    for (((i)) = (1); ((i)) <= ((s2.cnt)); ((i))++)
      fa[i][j] = fa[fa[i][j - 1]][j - 1];
  dfs2(1);
  cout << ans << endl;
  return 0;
}

### Prompt

In Cpp, your task is to solve the following 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.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
inline void read(int &x) {
  int v = 0, f = 1;
  char c = getchar();
  while (!isdigit(c) && c != '-') c = getchar();
  if (c == '-')
    f = -1;
  else
    v = (c & 15);
  while (isdigit(c = getchar())) v = (v << 1) + (v << 3) + (c & 15);
  x = v * f;
}
inline void read(long long &x) {
  long long v = 0ll, f = 1ll;
  char c = getchar();
  while (!isdigit(c) && c != '-') c = getchar();
  if (c == '-')
    f = -1;
  else
    v = (c & 15);
  while (isdigit(c = getchar())) v = (v << 1) + (v << 3) + (c & 15);
  x = v * f;
}
inline void readc(char &x) {
  char c;
  while (((c = getchar()) == ' ') || c == '\n')
    ;
  x = c;
}
int n, m, i, j;
long long ans;
string st;
struct sam {
  int fa[200005], l[200005], ch[200005][26], cnt, lst, ed[200005], mp[200005];
  void init() { cnt = lst = 1; }
  void ins(char c, int i) {
    int np = ++cnt, p = lst;
    lst = np;
    l[np] = l[p] + 1;
    ed[np] = i;
    mp[i] = np;
    for (; p && !ch[p][c - 'a']; p = fa[p]) ch[p][c - 'a'] = np;
    if (!p) {
      fa[np] = 1;
      return;
    }
    int q = ch[p][c - 'a'];
    if (l[p] + 1 == l[q]) {
      fa[np] = q;
      return;
    }
    int nq = ++cnt;
    l[nq] = l[p] + 1;
    fa[nq] = fa[q];
    fa[q] = fa[np] = nq;
    memcpy(ch[nq], ch[q], sizeof(ch[q]));
    for (; p && ch[p][c - 'a'] == q; p = fa[p]) ch[p][c - 'a'] = nq;
  }
  long long count() {
    long long s = 0;
    int i;
    for ((i) = (2); (i) <= (cnt); (i)++) {
      s += l[i] - l[fa[i]];
    }
    return s;
  }
} s1, s2;
int dep[200005], fa[200005][19];
vector<int> e1[200005], e2[200005];
int ti, dfn[200005], mp[200005];
void dfs1(int x) {
  mp[dfn[x] = ++ti] = x;
  for (__typeof((e2[x]).begin()) it = (e2[x]).begin(); it != (e2[x]).end();
       it++) {
    fa[*it][0] = x;
    dep[*it] = dep[x] + 1;
    dfs1(*it);
  }
}
int lca(int x, int y) {
  if (dep[x] < dep[y]) swap(x, y);
  int t = dep[x] - dep[y], i;
  for ((i) = (18); (i) >= (0); (i)--)
    if ((t >> i) & 1) x = fa[x][i];
  if (x == y) return x;
  for ((i) = (18); (i) >= (0); (i)--)
    if (fa[x][i] != fa[y][i]) {
      x = fa[x][i];
      y = fa[y][i];
    }
  return fa[x][0];
}
int dis(int x, int y) { return s2.l[x] + s2.l[y] - 2 * s2.l[lca(x, y)]; }
int rt[200005];
int lc[4000005], rc[4000005], cnt;
struct nd {
  int l, r;
  long long res;
} tr[4000005];
nd merge(nd x, nd y) {
  nd z;
  z.l = x.l;
  z.r = y.r;
  z.res = x.res + y.res + dis(x.r, y.l);
  return z;
}
void pushup(int x) {
  if (!lc[x])
    tr[x] = tr[rc[x]];
  else if (!rc[x])
    tr[x] = tr[lc[x]];
  else
    tr[x] = merge(tr[lc[x]], tr[rc[x]]);
}
void update(int &x, int l, int r, int y) {
  if (!x) x = ++cnt;
  if (l == r) {
    tr[x] = (nd){mp[y], mp[y], 0};
    return;
  }
  int mid = (l + r) / 2;
  if (y <= mid)
    update(lc[x], l, mid, y);
  else
    update(rc[x], mid + 1, r, y);
  pushup(x);
}
void merge(int &x, int y) {
  if (!x || !y) {
    x = x + y;
    return;
  }
  merge(lc[x], lc[y]);
  merge(rc[x], rc[y]);
  pushup(x);
}
void dfs2(int x) {
  if (s1.ed[x] && s1.ed[x] <= n - 2) {
    update(rt[x], 1, ti, dfn[s2.mp[s1.ed[x] + 2]]);
  }
  for (__typeof((e1[x]).begin()) it = (e1[x]).begin(); it != (e1[x]).end();
       it++) {
    dfs2(*it);
    merge(rt[x], rt[*it]);
  }
  ans += 1ll * (s1.l[x] - s1.l[s1.fa[x]]) *
         (tr[rt[x]].res + dis(tr[rt[x]].l, 1) + dis(1, tr[rt[x]].r)) / 2;
}
int main() {
  ios_base::sync_with_stdio(false);
  ;
  cin >> st;
  n = st.size();
  st = " " + st;
  ans = 2;
  s1.init();
  s2.init();
  for (((i)) = (1); ((i)) <= ((n - 1)); ((i))++) s1.ins(st[i], i);
  ans += s1.count();
  s1.ins(st[n], n);
  ans += s1.count();
  for (((i)) = (1); ((i)) <= ((n - 1)); ((i))++)
    s2.ins(st[n - i + 1], n - i + 1);
  ans += s2.count();
  s2.ins(st[1], 1);
  for ((i) = (2); (i) <= (s1.cnt); (i)++) e1[s1.fa[i]].push_back(i);
  for ((i) = (2); (i) <= (s2.cnt); (i)++) e2[s2.fa[i]].push_back(i);
  dfs1(1);
  for (((j)) = (1); ((j)) <= ((18)); ((j))++)
    for (((i)) = (1); ((i)) <= ((s2.cnt)); ((i))++)
      fa[i][j] = fa[fa[i][j - 1]][j - 1];
  dfs2(1);
  cout << ans << endl;
  return 0;
}

```