#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 7, M = 30;
int n;
char s[N];
long long sux;
namespace sam1 {
int tot, lst = 1, nxt = 1, fa[N], opt[N], dfn[N], pos[N], len[N], siz[N],
         dep[N], ch[N][M];
vector<int> v[N];
inline void ins(int u) {
  int p = lst, np = ++nxt;
  len[np] = len[p] + 1;
  lst = nxt, siz[nxt] = 1;
  while (!ch[p][u] && p) ch[p][u] = np, p = fa[p];
  if (!p) {
    fa[np] = 1;
    return;
  }
  int q = ch[p][u];
  if (len[q] == len[p] + 1) {
    fa[np] = q;
    return;
  }
  int nq = ++nxt;
  memcpy(ch[nq], ch[q], sizeof(ch[q])), fa[nq] = fa[q], fa[np] = nq, fa[q] = nq;
  len[nq] = len[p] + 1;
  while (ch[p][u] == q) ch[p][u] = nq, p = fa[p];
}
inline void dfs(int u) {
  if (opt[u] == n) siz[u] = 0;
  int len = v[u].size();
  ch[u][0] = fa[u], dfn[u] = ++tot;
  for (int i = 1; i <= 20; i++) ch[u][i] = ch[ch[u][i - 1]][i - 1];
  for (int i = 0; i < len; i++) {
    int x = v[u][i];
    dep[x] = dep[u] + 1, dfs(x), siz[u] += siz[x];
  }
}
inline int lca(int u, int v) {
  if (!u || !v) return (u + v);
  if (dep[u] < dep[v]) swap(u, v);
  for (int i = 0; i <= 18; i++)
    if ((1 << i) & (dep[u] - dep[v])) u = ch[u][i];
  if (u == v) return u;
  for (int i = 18; i >= 0; i--)
    if (ch[u][i] != ch[v][i]) u = ch[u][i], v = ch[v][i];
  return ch[u][0];
}
inline void init() {
  for (int i = 2; i <= nxt; i++) v[fa[i]].push_back(i);
  memset(ch, 0, sizeof(ch)), dfs(1);
}
}  // namespace sam1
namespace sam2 {
struct node {
  int u;
} g;
inline bool operator<(node a, node b) {
  return sam1::dfn[a.u] < sam1::dfn[b.u];
}
long long ans[N];
int lst = 1, nxt = 1, fa[N], ft[N], pt[N], pos[N], len[N], siz[N], dep[N],
    opt[N], ch[N][M];
vector<int> v[N];
set<node> f[N];
inline void ins(int u) {
  int p = lst, np = ++nxt;
  len[np] = len[p] + 1;
  lst = nxt, siz[nxt] = 1;
  while (!ch[p][u] && p) ch[p][u] = np, p = fa[p];
  if (!p) {
    fa[np] = 1;
    return;
  }
  int q = ch[p][u];
  if (len[q] == len[p] + 1) {
    fa[np] = q;
    return;
  }
  int nq = ++nxt;
  memcpy(ch[nq], ch[q], sizeof(ch[q])), fa[nq] = fa[q], fa[np] = nq, fa[q] = nq;
  len[nq] = len[p] + 1;
  while (ch[p][u] == q) ch[p][u] = nq, p = fa[p];
}
inline void addit(int u, int x) {
  pt[u] = sam1::lca(pt[u], x);
  int xt = f[u].size();
  if (xt == 0)
    g.u = x, f[u].insert(g);
  else if (xt == 1) {
    ans[u] += sam1::len[x] * 2;
    g = *f[u].rbegin(), ans[u] -= sam1::len[sam1::lca(g.u, x)] * 4;
    ans[u] += sam1::len[g.u] * 2, g.u = x, f[u].insert(g);
  } else {
    g.u = x;
    f[u].insert(g);
    node a, b;
    if ((*f[u].find(g)).u == (*f[u].begin()).u)
      a = *f[u].rbegin();
    else
      a = (*--(f[u].find(g)));
    if ((*f[u].find(g)).u == (*f[u].rbegin()).u)
      b = *f[u].begin();
    else
      b = (*++(f[u].find(g)));
    ans[u] = ans[u] + sam1::len[a.u] + sam1::len[x] -
             sam1::len[sam1::lca(a.u, x)] * 2;
    ans[u] = ans[u] + sam1::len[b.u] + sam1::len[x] -
             sam1::len[sam1::lca(b.u, x)] * 2;
    ans[u] = ans[u] - sam1::len[a.u] - sam1::len[b.u] +
             sam1::len[sam1::lca(a.u, b.u)] * 2;
  }
}
inline int merge(int u, int v) {
  if (f[u].size() < f[v].size()) swap(u, v);
  while (f[v].size()) {
    node c = *f[v].rbegin();
    f[v].erase(c);
    addit(u, c.u);
  }
  return u;
}
inline void dfs(int u) {
  if (opt[u] == 1) siz[u] = 0;
  int len = v[u].size();
  ch[u][0] = fa[u], ft[u] = u;
  for (int i = 1; i <= 20; i++) ch[u][i] = ch[ch[u][i - 1]][i - 1];
  for (int i = 0; i < len; i++) {
    int x = v[u][i];
    dep[x] = dep[u] + 1, dfs(x), ft[u] = merge(ft[u], ft[x]), siz[u] += siz[x];
  }
  if (opt[u] - 2 > 0 && opt[u]) addit(ft[u], sam1::pos[opt[u] - 2]);
  sux = sux + 1ll * (sam2::len[u] - sam2::len[fa[u]]) *
                  (ans[ft[u]] + 2 * sam1::len[pt[ft[u]]]) / 2;
  sux += sam2::len[u] - sam2::len[fa[u]];
}
inline int lca(int u, int v) {
  if (dep[u] < dep[v]) swap(u, v);
  for (int i = 0; i <= 18; i++)
    if ((1 << i) & (dep[u] - dep[v])) u = ch[u][i];
  if (u == v) return u;
  for (int i = 18; i >= 0; i--)
    if (ch[u][i] != ch[v][i]) u = ch[u][i], v = ch[v][i];
  return ch[u][0];
}
inline void init() {
  for (int i = 2; i <= nxt; i++) v[fa[i]].push_back(i);
  memset(ch, 0, sizeof(ch)), dfs(1);
}
}  // namespace sam2
namespace sam3 {
int lst = 1, nxt = 1, fa[N], ft[N], pos[N], len[N], siz[N], dep[N], opt[N],
    ch[N][M];
vector<int> v[N];
inline void ins(int u) {
  int p = lst, np = ++nxt;
  len[np] = len[p] + 1;
  lst = nxt, siz[nxt] = 1;
  while (!ch[p][u] && p) ch[p][u] = np, p = fa[p];
  if (!p) {
    fa[np] = 1;
    return;
  }
  int q = ch[p][u];
  if (len[q] == len[p] + 1) {
    fa[np] = q;
    return;
  }
  int nq = ++nxt;
  memcpy(ch[nq], ch[q], sizeof(ch[q])), fa[nq] = fa[q], fa[np] = nq, fa[q] = nq;
  len[nq] = len[p] + 1;
  while (ch[p][u] == q) ch[p][u] = nq, p = fa[p];
}
inline void dfs(int u) {
  int len = v[u].size();
  ch[u][0] = fa[u], ft[u] = u;
  for (int i = 1; i <= 20; i++) ch[u][i] = ch[ch[u][i - 1]][i - 1];
  for (int i = 0; i < len; i++) {
    int x = v[u][i];
    dep[x] = dep[u] + 1, dfs(x), siz[u] += siz[x];
  }
  sux += sam3::len[u] - sam3::len[fa[u]];
}
inline void init() {
  for (int i = 2; i <= nxt; i++) v[fa[i]].push_back(i);
  memset(ch, 0, sizeof(ch)), dfs(1);
}
}  // namespace sam3
namespace sam4 {
int lst = 1, nxt = 1, fa[N], ft[N], pos[N], len[N], siz[N], dep[N], opt[N],
    ch[N][M];
vector<int> v[N];
inline void ins(int u) {
  int p = lst, np = ++nxt;
  len[np] = len[p] + 1;
  lst = nxt, siz[nxt] = 1;
  while (!ch[p][u] && p) ch[p][u] = np, p = fa[p];
  if (!p) {
    fa[np] = 1;
    return;
  }
  int q = ch[p][u];
  if (len[q] == len[p] + 1) {
    fa[np] = q;
    return;
  }
  int nq = ++nxt;
  memcpy(ch[nq], ch[q], sizeof(ch[q])), fa[nq] = fa[q], fa[np] = nq, fa[q] = nq;
  len[nq] = len[p] + 1;
  while (ch[p][u] == q) ch[p][u] = nq, p = fa[p];
}
inline void dfs(int u) {
  int len = v[u].size();
  ch[u][0] = fa[u], ft[u] = u;
  for (int i = 1; i <= 20; i++) ch[u][i] = ch[ch[u][i - 1]][i - 1];
  for (int i = 0; i < len; i++) {
    int x = v[u][i];
    dep[x] = dep[u] + 1, dfs(x), siz[u] += siz[x];
  }
  sux += sam4::len[u] - sam4::len[fa[u]];
}
inline void init() {
  for (int i = 2; i <= nxt; i++) v[fa[i]].push_back(i);
  memset(ch, 0, sizeof(ch)), dfs(1);
}
}  // namespace sam4
int main() {
  scanf("%s", s + 1), n = strlen(s + 1);
  for (int i = 1; i <= n; i++)
    sam1::opt[sam1::nxt + 1] = i, sam1::pos[i] = sam1::nxt + 1,
                          sam1::ins(s[i] - 'a');
  for (int i = n; i >= 1; i--)
    sam2::opt[sam2::nxt + 1] = i, sam2::pos[i] = sam2::nxt + 1,
                          sam2::ins(s[i] - 'a');
  for (int i = 1; i < n; i++) sam3::ins(s[i] - 'a');
  for (int i = n; i > 1; i--) sam4::ins(s[i] - 'a');
  sam1::init();
  sam2::init();
  sam3::init();
  sam4::init();
  cout << sux + 2 << endl;
  return 0;
}

### Prompt

Construct a CPP code solution to the problem outlined:

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 N = 2e5 + 7, M = 30;
int n;
char s[N];
long long sux;
namespace sam1 {
int tot, lst = 1, nxt = 1, fa[N], opt[N], dfn[N], pos[N], len[N], siz[N],
         dep[N], ch[N][M];
vector<int> v[N];
inline void ins(int u) {
  int p = lst, np = ++nxt;
  len[np] = len[p] + 1;
  lst = nxt, siz[nxt] = 1;
  while (!ch[p][u] && p) ch[p][u] = np, p = fa[p];
  if (!p) {
    fa[np] = 1;
    return;
  }
  int q = ch[p][u];
  if (len[q] == len[p] + 1) {
    fa[np] = q;
    return;
  }
  int nq = ++nxt;
  memcpy(ch[nq], ch[q], sizeof(ch[q])), fa[nq] = fa[q], fa[np] = nq, fa[q] = nq;
  len[nq] = len[p] + 1;
  while (ch[p][u] == q) ch[p][u] = nq, p = fa[p];
}
inline void dfs(int u) {
  if (opt[u] == n) siz[u] = 0;
  int len = v[u].size();
  ch[u][0] = fa[u], dfn[u] = ++tot;
  for (int i = 1; i <= 20; i++) ch[u][i] = ch[ch[u][i - 1]][i - 1];
  for (int i = 0; i < len; i++) {
    int x = v[u][i];
    dep[x] = dep[u] + 1, dfs(x), siz[u] += siz[x];
  }
}
inline int lca(int u, int v) {
  if (!u || !v) return (u + v);
  if (dep[u] < dep[v]) swap(u, v);
  for (int i = 0; i <= 18; i++)
    if ((1 << i) & (dep[u] - dep[v])) u = ch[u][i];
  if (u == v) return u;
  for (int i = 18; i >= 0; i--)
    if (ch[u][i] != ch[v][i]) u = ch[u][i], v = ch[v][i];
  return ch[u][0];
}
inline void init() {
  for (int i = 2; i <= nxt; i++) v[fa[i]].push_back(i);
  memset(ch, 0, sizeof(ch)), dfs(1);
}
}  // namespace sam1
namespace sam2 {
struct node {
  int u;
} g;
inline bool operator<(node a, node b) {
  return sam1::dfn[a.u] < sam1::dfn[b.u];
}
long long ans[N];
int lst = 1, nxt = 1, fa[N], ft[N], pt[N], pos[N], len[N], siz[N], dep[N],
    opt[N], ch[N][M];
vector<int> v[N];
set<node> f[N];
inline void ins(int u) {
  int p = lst, np = ++nxt;
  len[np] = len[p] + 1;
  lst = nxt, siz[nxt] = 1;
  while (!ch[p][u] && p) ch[p][u] = np, p = fa[p];
  if (!p) {
    fa[np] = 1;
    return;
  }
  int q = ch[p][u];
  if (len[q] == len[p] + 1) {
    fa[np] = q;
    return;
  }
  int nq = ++nxt;
  memcpy(ch[nq], ch[q], sizeof(ch[q])), fa[nq] = fa[q], fa[np] = nq, fa[q] = nq;
  len[nq] = len[p] + 1;
  while (ch[p][u] == q) ch[p][u] = nq, p = fa[p];
}
inline void addit(int u, int x) {
  pt[u] = sam1::lca(pt[u], x);
  int xt = f[u].size();
  if (xt == 0)
    g.u = x, f[u].insert(g);
  else if (xt == 1) {
    ans[u] += sam1::len[x] * 2;
    g = *f[u].rbegin(), ans[u] -= sam1::len[sam1::lca(g.u, x)] * 4;
    ans[u] += sam1::len[g.u] * 2, g.u = x, f[u].insert(g);
  } else {
    g.u = x;
    f[u].insert(g);
    node a, b;
    if ((*f[u].find(g)).u == (*f[u].begin()).u)
      a = *f[u].rbegin();
    else
      a = (*--(f[u].find(g)));
    if ((*f[u].find(g)).u == (*f[u].rbegin()).u)
      b = *f[u].begin();
    else
      b = (*++(f[u].find(g)));
    ans[u] = ans[u] + sam1::len[a.u] + sam1::len[x] -
             sam1::len[sam1::lca(a.u, x)] * 2;
    ans[u] = ans[u] + sam1::len[b.u] + sam1::len[x] -
             sam1::len[sam1::lca(b.u, x)] * 2;
    ans[u] = ans[u] - sam1::len[a.u] - sam1::len[b.u] +
             sam1::len[sam1::lca(a.u, b.u)] * 2;
  }
}
inline int merge(int u, int v) {
  if (f[u].size() < f[v].size()) swap(u, v);
  while (f[v].size()) {
    node c = *f[v].rbegin();
    f[v].erase(c);
    addit(u, c.u);
  }
  return u;
}
inline void dfs(int u) {
  if (opt[u] == 1) siz[u] = 0;
  int len = v[u].size();
  ch[u][0] = fa[u], ft[u] = u;
  for (int i = 1; i <= 20; i++) ch[u][i] = ch[ch[u][i - 1]][i - 1];
  for (int i = 0; i < len; i++) {
    int x = v[u][i];
    dep[x] = dep[u] + 1, dfs(x), ft[u] = merge(ft[u], ft[x]), siz[u] += siz[x];
  }
  if (opt[u] - 2 > 0 && opt[u]) addit(ft[u], sam1::pos[opt[u] - 2]);
  sux = sux + 1ll * (sam2::len[u] - sam2::len[fa[u]]) *
                  (ans[ft[u]] + 2 * sam1::len[pt[ft[u]]]) / 2;
  sux += sam2::len[u] - sam2::len[fa[u]];
}
inline int lca(int u, int v) {
  if (dep[u] < dep[v]) swap(u, v);
  for (int i = 0; i <= 18; i++)
    if ((1 << i) & (dep[u] - dep[v])) u = ch[u][i];
  if (u == v) return u;
  for (int i = 18; i >= 0; i--)
    if (ch[u][i] != ch[v][i]) u = ch[u][i], v = ch[v][i];
  return ch[u][0];
}
inline void init() {
  for (int i = 2; i <= nxt; i++) v[fa[i]].push_back(i);
  memset(ch, 0, sizeof(ch)), dfs(1);
}
}  // namespace sam2
namespace sam3 {
int lst = 1, nxt = 1, fa[N], ft[N], pos[N], len[N], siz[N], dep[N], opt[N],
    ch[N][M];
vector<int> v[N];
inline void ins(int u) {
  int p = lst, np = ++nxt;
  len[np] = len[p] + 1;
  lst = nxt, siz[nxt] = 1;
  while (!ch[p][u] && p) ch[p][u] = np, p = fa[p];
  if (!p) {
    fa[np] = 1;
    return;
  }
  int q = ch[p][u];
  if (len[q] == len[p] + 1) {
    fa[np] = q;
    return;
  }
  int nq = ++nxt;
  memcpy(ch[nq], ch[q], sizeof(ch[q])), fa[nq] = fa[q], fa[np] = nq, fa[q] = nq;
  len[nq] = len[p] + 1;
  while (ch[p][u] == q) ch[p][u] = nq, p = fa[p];
}
inline void dfs(int u) {
  int len = v[u].size();
  ch[u][0] = fa[u], ft[u] = u;
  for (int i = 1; i <= 20; i++) ch[u][i] = ch[ch[u][i - 1]][i - 1];
  for (int i = 0; i < len; i++) {
    int x = v[u][i];
    dep[x] = dep[u] + 1, dfs(x), siz[u] += siz[x];
  }
  sux += sam3::len[u] - sam3::len[fa[u]];
}
inline void init() {
  for (int i = 2; i <= nxt; i++) v[fa[i]].push_back(i);
  memset(ch, 0, sizeof(ch)), dfs(1);
}
}  // namespace sam3
namespace sam4 {
int lst = 1, nxt = 1, fa[N], ft[N], pos[N], len[N], siz[N], dep[N], opt[N],
    ch[N][M];
vector<int> v[N];
inline void ins(int u) {
  int p = lst, np = ++nxt;
  len[np] = len[p] + 1;
  lst = nxt, siz[nxt] = 1;
  while (!ch[p][u] && p) ch[p][u] = np, p = fa[p];
  if (!p) {
    fa[np] = 1;
    return;
  }
  int q = ch[p][u];
  if (len[q] == len[p] + 1) {
    fa[np] = q;
    return;
  }
  int nq = ++nxt;
  memcpy(ch[nq], ch[q], sizeof(ch[q])), fa[nq] = fa[q], fa[np] = nq, fa[q] = nq;
  len[nq] = len[p] + 1;
  while (ch[p][u] == q) ch[p][u] = nq, p = fa[p];
}
inline void dfs(int u) {
  int len = v[u].size();
  ch[u][0] = fa[u], ft[u] = u;
  for (int i = 1; i <= 20; i++) ch[u][i] = ch[ch[u][i - 1]][i - 1];
  for (int i = 0; i < len; i++) {
    int x = v[u][i];
    dep[x] = dep[u] + 1, dfs(x), siz[u] += siz[x];
  }
  sux += sam4::len[u] - sam4::len[fa[u]];
}
inline void init() {
  for (int i = 2; i <= nxt; i++) v[fa[i]].push_back(i);
  memset(ch, 0, sizeof(ch)), dfs(1);
}
}  // namespace sam4
int main() {
  scanf("%s", s + 1), n = strlen(s + 1);
  for (int i = 1; i <= n; i++)
    sam1::opt[sam1::nxt + 1] = i, sam1::pos[i] = sam1::nxt + 1,
                          sam1::ins(s[i] - 'a');
  for (int i = n; i >= 1; i--)
    sam2::opt[sam2::nxt + 1] = i, sam2::pos[i] = sam2::nxt + 1,
                          sam2::ins(s[i] - 'a');
  for (int i = 1; i < n; i++) sam3::ins(s[i] - 'a');
  for (int i = n; i > 1; i--) sam4::ins(s[i] - 'a');
  sam1::init();
  sam2::init();
  sam3::init();
  sam4::init();
  cout << sux + 2 << endl;
  return 0;
}

```