#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int gi() {
  int x = 0, o = 1;
  char ch = getchar();
  while (!isdigit(ch) && ch != '-') ch = getchar();
  if (ch == '-') o = -1, ch = getchar();
  while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
  return x * o;
}
char s[N], t[N];
int n;
long long ans;
class SAM {
 public:
  int ch[N][26], fa[N], len[N], tt = 1, lst = 1, son[N], siz[N], dep[N], top[N],
                                tim, id[N], pos[N], dfn[N];
  vector<int> E[N];
  void extend(int c) {
    int p = lst, np = ++tt;
    lst = np;
    len[np] = len[p] + 1;
    for (; p && !ch[p][c]; p = fa[p]) ch[p][c] = np;
    if (!p)
      fa[np] = 1;
    else {
      int q = ch[p][c];
      if (len[p] + 1 == len[q])
        fa[np] = q;
      else {
        int nq = ++tt;
        len[nq] = len[p] + 1;
        memcpy(ch[nq], ch[q], sizeof(ch[q]));
        fa[nq] = fa[q];
        fa[q] = fa[np] = nq;
        for (; ch[p][c] == q; p = fa[p]) ch[p][c] = nq;
      }
    }
  }
  long long count() {
    long long ret = 0;
    for (int i = 2; i <= tt; i++) ret += len[i] - len[fa[i]];
    return ret;
  }
  void build(char *s, bool fl = 0) {
    int n = strlen(s + 1);
    for (int i = 1; i <= n; i++) {
      extend(s[i] - 'a');
      if (fl) {
        if (i < n) pos[n - i - 1] = lst;
      } else
        id[lst] = i;
    }
    for (int i = 2; i <= tt; i++) E[fa[i]].push_back(i);
  }
  void dfs1(int u) {
    siz[u] = 1;
    dep[u] = dep[fa[u]] + 1;
    dfn[u] = ++tim;
    for (auto v : E[u])
      if (v != fa[u]) {
        dfs1(v);
        siz[u] += siz[v];
        if (siz[son[u]] < siz[v]) son[u] = v;
      }
  }
  void dfs2(int u, int tp) {
    top[u] = tp;
    if (son[u]) dfs2(son[u], tp);
    for (auto v : E[u])
      if (v != fa[u] && v != son[u]) dfs2(v, v);
  }
  int lca(int u, int v) {
    while (top[u] != top[v]) {
      if (dep[top[u]] < dep[top[v]]) swap(u, v);
      u = fa[top[u]];
    }
    return dep[u] < dep[v] ? u : v;
  }
} S2, S3, S4;
struct cmp {
  bool operator()(int a, int b) { return S2.dfn[a] < S2.dfn[b]; }
};
struct dat {
  long long len;
  set<int, cmp> s;
  void insert(int v) {
    int p = 0, q = 0;
    auto it = s.lower_bound(v);
    if (it != s.end()) q = *it;
    if (it != s.begin()) --it, p = *it;
    len += S2.len[v];
    if (p) len -= S2.len[S2.lca(p, v)];
    if (q) len -= S2.len[S2.lca(q, v)];
    if (p && q) len += S2.len[S2.lca(p, q)];
    s.insert(v);
  }
  void merge(dat &A) {
    if (int(s.size()) < int(A.s.size())) swap(s, A.s), swap(len, A.len);
    for (auto x : A.s) insert(x);
    A.s.clear();
  }
};
class SAM1 : public SAM {
 public:
  dat S[N];
  void work(int u) {
    if (id[u]) {
      if (S2.pos[id[u]]) S[u].insert(S2.pos[id[u]]);
    }
    for (auto v : E[u]) work(v), S[u].merge(S[v]);
    if (u > 1) ans += S[u].len * (len[u] - len[fa[u]]);
  }
} S1;
int main() {
  scanf("%s", s + 1);
  n = strlen(s + 1);
  S1.build(s);
  reverse(s + 1, s + n + 1);
  S2.build(s, 1);
  ans = S1.count() + 1;
  S2.dfs1(1);
  S2.dfs2(1, 1);
  S1.work(1);
  for (int i = 1; i < n; i++) t[i] = s[i + 1];
  t[n] = '\0';
  S3.build(t);
  ans += S3.count();
  for (int i = 1; i < n; i++) t[i] = s[i];
  t[n] = '\0';
  S4.build(t);
  ans += S4.count();
  cout << ans + 1;
  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 + 10;
int gi() {
  int x = 0, o = 1;
  char ch = getchar();
  while (!isdigit(ch) && ch != '-') ch = getchar();
  if (ch == '-') o = -1, ch = getchar();
  while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
  return x * o;
}
char s[N], t[N];
int n;
long long ans;
class SAM {
 public:
  int ch[N][26], fa[N], len[N], tt = 1, lst = 1, son[N], siz[N], dep[N], top[N],
                                tim, id[N], pos[N], dfn[N];
  vector<int> E[N];
  void extend(int c) {
    int p = lst, np = ++tt;
    lst = np;
    len[np] = len[p] + 1;
    for (; p && !ch[p][c]; p = fa[p]) ch[p][c] = np;
    if (!p)
      fa[np] = 1;
    else {
      int q = ch[p][c];
      if (len[p] + 1 == len[q])
        fa[np] = q;
      else {
        int nq = ++tt;
        len[nq] = len[p] + 1;
        memcpy(ch[nq], ch[q], sizeof(ch[q]));
        fa[nq] = fa[q];
        fa[q] = fa[np] = nq;
        for (; ch[p][c] == q; p = fa[p]) ch[p][c] = nq;
      }
    }
  }
  long long count() {
    long long ret = 0;
    for (int i = 2; i <= tt; i++) ret += len[i] - len[fa[i]];
    return ret;
  }
  void build(char *s, bool fl = 0) {
    int n = strlen(s + 1);
    for (int i = 1; i <= n; i++) {
      extend(s[i] - 'a');
      if (fl) {
        if (i < n) pos[n - i - 1] = lst;
      } else
        id[lst] = i;
    }
    for (int i = 2; i <= tt; i++) E[fa[i]].push_back(i);
  }
  void dfs1(int u) {
    siz[u] = 1;
    dep[u] = dep[fa[u]] + 1;
    dfn[u] = ++tim;
    for (auto v : E[u])
      if (v != fa[u]) {
        dfs1(v);
        siz[u] += siz[v];
        if (siz[son[u]] < siz[v]) son[u] = v;
      }
  }
  void dfs2(int u, int tp) {
    top[u] = tp;
    if (son[u]) dfs2(son[u], tp);
    for (auto v : E[u])
      if (v != fa[u] && v != son[u]) dfs2(v, v);
  }
  int lca(int u, int v) {
    while (top[u] != top[v]) {
      if (dep[top[u]] < dep[top[v]]) swap(u, v);
      u = fa[top[u]];
    }
    return dep[u] < dep[v] ? u : v;
  }
} S2, S3, S4;
struct cmp {
  bool operator()(int a, int b) { return S2.dfn[a] < S2.dfn[b]; }
};
struct dat {
  long long len;
  set<int, cmp> s;
  void insert(int v) {
    int p = 0, q = 0;
    auto it = s.lower_bound(v);
    if (it != s.end()) q = *it;
    if (it != s.begin()) --it, p = *it;
    len += S2.len[v];
    if (p) len -= S2.len[S2.lca(p, v)];
    if (q) len -= S2.len[S2.lca(q, v)];
    if (p && q) len += S2.len[S2.lca(p, q)];
    s.insert(v);
  }
  void merge(dat &A) {
    if (int(s.size()) < int(A.s.size())) swap(s, A.s), swap(len, A.len);
    for (auto x : A.s) insert(x);
    A.s.clear();
  }
};
class SAM1 : public SAM {
 public:
  dat S[N];
  void work(int u) {
    if (id[u]) {
      if (S2.pos[id[u]]) S[u].insert(S2.pos[id[u]]);
    }
    for (auto v : E[u]) work(v), S[u].merge(S[v]);
    if (u > 1) ans += S[u].len * (len[u] - len[fa[u]]);
  }
} S1;
int main() {
  scanf("%s", s + 1);
  n = strlen(s + 1);
  S1.build(s);
  reverse(s + 1, s + n + 1);
  S2.build(s, 1);
  ans = S1.count() + 1;
  S2.dfs1(1);
  S2.dfs2(1, 1);
  S1.work(1);
  for (int i = 1; i < n; i++) t[i] = s[i + 1];
  t[n] = '\0';
  S3.build(t);
  ans += S3.count();
  for (int i = 1; i < n; i++) t[i] = s[i];
  t[n] = '\0';
  S4.build(t);
  ans += S4.count();
  cout << ans + 1;
  return 0;
}

```