#include <bits/stdc++.h>
using namespace std;
const int mxn = 200010;
int lens;
char s[mxn];
long long ans;
namespace SAM {
int n = 1, cur = 1, trans[mxn][26], son[mxn][26], fa[mxn], len[mxn], id[mxn];
int ins(int u, int c, int idd) {
  int x = ++n, v;
  len[x] = len[u] + 1, id[x] = idd;
  for (; u && !trans[u][c]; trans[u][c] = x, u = fa[u])
    ;
  if (!u)
    fa[x] = 1;
  else if (len[v = trans[u][c]] == len[u] + 1)
    fa[x] = v;
  else {
    len[++n] = len[u] + 1, id[n] = idd;
    fa[n] = fa[v], fa[x] = fa[v] = n;
    for (int i = 0; i < 26; ++i) trans[n][i] = trans[v][i];
    for (; u && trans[u][c] == v; trans[u][c] = n, u = fa[u])
      ;
  }
  return x;
}
int m, sa[mxn], rnk[mxn], st[mxn][20], lg[mxn];
int dfs(int u) {
  int ret = 0;
  if (id[u] + len[u] == lens) sa[++m] = id[u] + 1, rnk[id[u] + 1] = m, ret = m;
  for (int i = 0; i < 26; ++i)
    if (son[u][i])
      if (ret)
        st[dfs(son[u][i])][0] = len[u];
      else
        ret = dfs(son[u][i]);
    else
      ;
  return ret;
}
void cal() {
  for (int i = 2; i <= n; ++i) ans += len[i] - len[fa[i]];
}
void init() {
  for (int i = lens - 1; i >= 0; --i) {
    if (!i) cal();
    cur = ins(cur, s[i] - 'a', i);
  }
  cal();
  for (int i = 2; i <= n; ++i) son[fa[i]][s[id[i] + len[fa[i]]] - 'a'] = i;
  dfs(1);
  for (int i = 2; i <= m; ++i) lg[i] = lg[i >> 1] + 1;
  for (int j = 1; j < 18; ++j)
    for (int i = 1; i + (1 << j) - 1 <= m; ++i)
      st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}
int lcp(int x, int y) {
  if (x > y) swap(x, y);
  ++x;
  int k = lg[y - x + 1];
  return min(st[x][k], st[y - (1 << k) + 1][k]);
}
}  // namespace SAM
using SAM::lcp;
const int mxN = 4000010;
int tot, pr[mxN], sc[mxN], lson[mxN], rson[mxN];
long long tr[mxN];
void pushup(int i) {
  if (!rson[i]) {
    tr[i] = tr[lson[i]], pr[i] = pr[lson[i]], sc[i] = sc[lson[i]];
    return;
  }
  if (!lson[i]) {
    tr[i] = tr[rson[i]], pr[i] = pr[rson[i]], sc[i] = sc[rson[i]];
    return;
  }
  tr[i] = tr[lson[i]] + tr[rson[i]] - lcp(sc[lson[i]], pr[rson[i]]);
  pr[i] = pr[lson[i]], sc[i] = sc[rson[i]];
}
void update(int &i, int l, int r, int p) {
  if (!i) i = ++tot;
  if (l == r) {
    tr[i] = lens - SAM::sa[l] + 1;
    pr[i] = sc[i] = l;
    return;
  }
  if (p <= ((l + r) >> 1))
    update(lson[i], l, ((l + r) >> 1), p);
  else
    update(rson[i], ((l + r) >> 1) + 1, r, p);
  pushup(i);
}
int mrg(int x, int y) {
  if (!x || !y) return x | y;
  lson[x] = mrg(lson[x], lson[y]);
  rson[x] = mrg(rson[x], rson[y]);
  if (lson[x] || rson[x]) pushup(x);
  return x;
}
int n = 1, cur = 1, trans[mxn][26], son[mxn][26], fa[mxn], len[mxn], id[mxn];
int ins(int u, int c, int idd) {
  int x = ++n, v;
  len[x] = len[u] + 1, id[x] = idd;
  for (; u && !trans[u][c]; trans[u][c] = x, u = fa[u])
    ;
  if (!u)
    fa[x] = 1;
  else if (len[v = trans[u][c]] == len[u] + 1)
    fa[x] = v;
  else {
    len[++n] = len[u] + 1, id[n] = idd;
    fa[n] = fa[v], fa[x] = fa[v] = n;
    for (int i = 0; i < 26; ++i) trans[n][i] = trans[v][i];
    for (; u && trans[u][c] == v; trans[u][c] = n, u = fa[u])
      ;
  }
  return x;
}
int rt[mxn];
void dfs(int u) {
  if (id[u] + 1 == len[u] && id[u] < lens - 2)
    update(rt[u], 1, lens, SAM::rnk[id[u] + 3]);
  for (int i = 0, v; i < 26; ++i)
    if (son[u][i]) {
      dfs(v = son[u][i]);
      rt[u] = mrg(rt[u], rt[v]);
    }
  ans += tr[rt[u]] * (len[u] - len[fa[u]]);
}
void cal() {
  for (int i = 2; i <= n; ++i) ans += len[i] - len[fa[i]];
}
void solve() {
  for (int i = 0; i < lens; ++i) {
    if (i == lens - 1) cal();
    cur = ins(cur, s[i] - 'a', i);
  }
  for (int i = 2; i <= n; ++i) son[fa[i]][s[id[i] - len[fa[i]]] - 'a'] = i;
  dfs(1);
}
int main() {
  scanf("%s", s);
  lens = strlen(s);
  SAM::init();
  solve();
  printf("%lld\n", ans + 2);
  return 0;
}

### Prompt

Your challenge is to write a CPP solution to 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;
const int mxn = 200010;
int lens;
char s[mxn];
long long ans;
namespace SAM {
int n = 1, cur = 1, trans[mxn][26], son[mxn][26], fa[mxn], len[mxn], id[mxn];
int ins(int u, int c, int idd) {
  int x = ++n, v;
  len[x] = len[u] + 1, id[x] = idd;
  for (; u && !trans[u][c]; trans[u][c] = x, u = fa[u])
    ;
  if (!u)
    fa[x] = 1;
  else if (len[v = trans[u][c]] == len[u] + 1)
    fa[x] = v;
  else {
    len[++n] = len[u] + 1, id[n] = idd;
    fa[n] = fa[v], fa[x] = fa[v] = n;
    for (int i = 0; i < 26; ++i) trans[n][i] = trans[v][i];
    for (; u && trans[u][c] == v; trans[u][c] = n, u = fa[u])
      ;
  }
  return x;
}
int m, sa[mxn], rnk[mxn], st[mxn][20], lg[mxn];
int dfs(int u) {
  int ret = 0;
  if (id[u] + len[u] == lens) sa[++m] = id[u] + 1, rnk[id[u] + 1] = m, ret = m;
  for (int i = 0; i < 26; ++i)
    if (son[u][i])
      if (ret)
        st[dfs(son[u][i])][0] = len[u];
      else
        ret = dfs(son[u][i]);
    else
      ;
  return ret;
}
void cal() {
  for (int i = 2; i <= n; ++i) ans += len[i] - len[fa[i]];
}
void init() {
  for (int i = lens - 1; i >= 0; --i) {
    if (!i) cal();
    cur = ins(cur, s[i] - 'a', i);
  }
  cal();
  for (int i = 2; i <= n; ++i) son[fa[i]][s[id[i] + len[fa[i]]] - 'a'] = i;
  dfs(1);
  for (int i = 2; i <= m; ++i) lg[i] = lg[i >> 1] + 1;
  for (int j = 1; j < 18; ++j)
    for (int i = 1; i + (1 << j) - 1 <= m; ++i)
      st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}
int lcp(int x, int y) {
  if (x > y) swap(x, y);
  ++x;
  int k = lg[y - x + 1];
  return min(st[x][k], st[y - (1 << k) + 1][k]);
}
}  // namespace SAM
using SAM::lcp;
const int mxN = 4000010;
int tot, pr[mxN], sc[mxN], lson[mxN], rson[mxN];
long long tr[mxN];
void pushup(int i) {
  if (!rson[i]) {
    tr[i] = tr[lson[i]], pr[i] = pr[lson[i]], sc[i] = sc[lson[i]];
    return;
  }
  if (!lson[i]) {
    tr[i] = tr[rson[i]], pr[i] = pr[rson[i]], sc[i] = sc[rson[i]];
    return;
  }
  tr[i] = tr[lson[i]] + tr[rson[i]] - lcp(sc[lson[i]], pr[rson[i]]);
  pr[i] = pr[lson[i]], sc[i] = sc[rson[i]];
}
void update(int &i, int l, int r, int p) {
  if (!i) i = ++tot;
  if (l == r) {
    tr[i] = lens - SAM::sa[l] + 1;
    pr[i] = sc[i] = l;
    return;
  }
  if (p <= ((l + r) >> 1))
    update(lson[i], l, ((l + r) >> 1), p);
  else
    update(rson[i], ((l + r) >> 1) + 1, r, p);
  pushup(i);
}
int mrg(int x, int y) {
  if (!x || !y) return x | y;
  lson[x] = mrg(lson[x], lson[y]);
  rson[x] = mrg(rson[x], rson[y]);
  if (lson[x] || rson[x]) pushup(x);
  return x;
}
int n = 1, cur = 1, trans[mxn][26], son[mxn][26], fa[mxn], len[mxn], id[mxn];
int ins(int u, int c, int idd) {
  int x = ++n, v;
  len[x] = len[u] + 1, id[x] = idd;
  for (; u && !trans[u][c]; trans[u][c] = x, u = fa[u])
    ;
  if (!u)
    fa[x] = 1;
  else if (len[v = trans[u][c]] == len[u] + 1)
    fa[x] = v;
  else {
    len[++n] = len[u] + 1, id[n] = idd;
    fa[n] = fa[v], fa[x] = fa[v] = n;
    for (int i = 0; i < 26; ++i) trans[n][i] = trans[v][i];
    for (; u && trans[u][c] == v; trans[u][c] = n, u = fa[u])
      ;
  }
  return x;
}
int rt[mxn];
void dfs(int u) {
  if (id[u] + 1 == len[u] && id[u] < lens - 2)
    update(rt[u], 1, lens, SAM::rnk[id[u] + 3]);
  for (int i = 0, v; i < 26; ++i)
    if (son[u][i]) {
      dfs(v = son[u][i]);
      rt[u] = mrg(rt[u], rt[v]);
    }
  ans += tr[rt[u]] * (len[u] - len[fa[u]]);
}
void cal() {
  for (int i = 2; i <= n; ++i) ans += len[i] - len[fa[i]];
}
void solve() {
  for (int i = 0; i < lens; ++i) {
    if (i == lens - 1) cal();
    cur = ins(cur, s[i] - 'a', i);
  }
  for (int i = 2; i <= n; ++i) son[fa[i]][s[id[i] - len[fa[i]]] - 'a'] = i;
  dfs(1);
}
int main() {
  scanf("%s", s);
  lens = strlen(s);
  SAM::init();
  solve();
  printf("%lld\n", ans + 2);
  return 0;
}

```