#include <bits/stdc++.h>
using namespace std;
void read(int &x) {
  char ch = getchar();
  x = 0;
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
}
const int N = 1e5 + 5, M = N << 1;
int n, tot = 1, lst = 1, ch[M][26], link[M], len[M];
char a[N];
void extend(int c) {
  int p = lst, np = lst = ++tot;
  len[np] = len[p] + 1;
  for (; p && !ch[p][c]; p = link[p]) ch[p][c] = np;
  if (!p) {
    link[np] = 1;
    return;
  }
  int q = ch[p][c];
  if (len[q] == len[p] + 1) {
    link[np] = q;
    return;
  }
  int nq = ++tot;
  memcpy(ch[nq], ch[q], 26 << 2), link[nq] = link[q];
  len[nq] = len[p] + 1, link[np] = link[q] = nq;
  for (; p && ch[p][c] == q; p = link[p]) ch[p][c] = nq;
}
vector<int> g[M];
int m = 1e5, sa[N], rk[N], c[N], id[N], t[N], h[N], rrk[N];
bool cmp(int x, int y, int w) {
  return rrk[x] == rrk[y] && rrk[x + w] == rrk[y + w];
}
void getsa() {
  for (int i = 1; i <= n; ++i) ++c[rk[i] = a[i]];
  for (int i = 1; i <= m; ++i) c[i] += c[i - 1];
  for (int i = n; i >= 1; --i) sa[c[rk[i]]--] = i;
  int p = 0;
  for (int w = 1; w < n; w <<= 1, m = p, p = 0) {
    for (int i = n; i > n - w; --i) id[++p] = i;
    for (int i = 1; i <= n; ++i)
      if (sa[i] > w) id[++p] = sa[i] - w;
    memset(c, 0, sizeof(c));
    for (int i = 1; i <= n; ++i) ++c[t[i] = rk[id[i]]];
    for (int i = 1; i <= m; ++i) c[i] += c[i - 1];
    for (int i = n; i >= 1; --i) sa[c[t[i]]--] = id[i];
    memcpy(rrk, rk, sizeof(rk));
    p = 0;
    for (int i = 1; i <= n; ++i) rk[sa[i]] = cmp(sa[i], sa[i - 1], w) ? p : ++p;
  }
  for (int i = 1, j = 0; i <= n; ++i) {
    if (j) --j;
    while (a[i + j] == a[sa[rk[i] - 1] + j]) ++j;
    h[rk[i]] = j;
  }
}
int st[N][20], lg[N];
void getst() {
  for (int i = 1; i <= n; ++i) st[i][0] = h[i];
  for (int j = 1; j <= 17; ++j)
    for (int i = 1; i + (1 << j) - 1 <= n; ++i)
      st[i][j] = min(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);
  for (int i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1;
}
int ask(int l, int r) {
  int t = lg[r - l + 1];
  return min(st[l][t], st[r - (1 << t) + 1][t]);
}
struct yxl {
  set<int> s;
  long long val;
  void init() { s.insert(0), s.insert(n + 1); }
  void ins(int x) {
    if (s.count(x)) return;
    int l = *(--s.lower_bound(x));
    int r = *s.upper_bound(x);
    val += n - sa[x] + 1;
    if (l >= 1) val -= ask(l + 1, x);
    if (r <= n) val -= ask(x + 1, r);
    if (l >= 1 && r <= n) val += ask(l + 1, r);
    s.insert(x);
  }
} s[M];
long long res;
void dfs(int u) {
  for (int v : g[u]) {
    dfs(v);
    if (s[v].s.size() > s[u].s.size()) swap(s[u], s[v]);
    for (int x : s[v].s) s[u].ins(x);
  }
  res += s[u].val * (len[u] - len[link[u]]);
}
signed main() {
  scanf("%s", a + 1);
  n = strlen(a + 1);
  for (int i = 1; i <= n; ++i) extend(a[i] - 'a');
  getsa();
  getst();
  for (int i = 1; i <= tot; ++i) res += len[i] - len[link[i]];
  int now = 1;
  for (int i = 1; i <= n; ++i) now = ch[now][a[i] - 'a'];
  for (int i = 1; i <= tot; ++i)
    if (i != now) res += len[i] - len[link[i]];
  for (int i = 1; i <= tot; ++i) g[link[i]].push_back(i), s[i].init();
  now = 1;
  s[now].ins(rk[2]);
  for (int i = 1; i <= n - 2; ++i) {
    s[now = ch[now][a[i] - 'a']].ins(rk[i + 2]);
  }
  dfs(1);
  res += s[1].val;
  printf("%lld\n", res + 2);
  return 0;
}

### Prompt

Please create a solution in CPP 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;
void read(int &x) {
  char ch = getchar();
  x = 0;
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
}
const int N = 1e5 + 5, M = N << 1;
int n, tot = 1, lst = 1, ch[M][26], link[M], len[M];
char a[N];
void extend(int c) {
  int p = lst, np = lst = ++tot;
  len[np] = len[p] + 1;
  for (; p && !ch[p][c]; p = link[p]) ch[p][c] = np;
  if (!p) {
    link[np] = 1;
    return;
  }
  int q = ch[p][c];
  if (len[q] == len[p] + 1) {
    link[np] = q;
    return;
  }
  int nq = ++tot;
  memcpy(ch[nq], ch[q], 26 << 2), link[nq] = link[q];
  len[nq] = len[p] + 1, link[np] = link[q] = nq;
  for (; p && ch[p][c] == q; p = link[p]) ch[p][c] = nq;
}
vector<int> g[M];
int m = 1e5, sa[N], rk[N], c[N], id[N], t[N], h[N], rrk[N];
bool cmp(int x, int y, int w) {
  return rrk[x] == rrk[y] && rrk[x + w] == rrk[y + w];
}
void getsa() {
  for (int i = 1; i <= n; ++i) ++c[rk[i] = a[i]];
  for (int i = 1; i <= m; ++i) c[i] += c[i - 1];
  for (int i = n; i >= 1; --i) sa[c[rk[i]]--] = i;
  int p = 0;
  for (int w = 1; w < n; w <<= 1, m = p, p = 0) {
    for (int i = n; i > n - w; --i) id[++p] = i;
    for (int i = 1; i <= n; ++i)
      if (sa[i] > w) id[++p] = sa[i] - w;
    memset(c, 0, sizeof(c));
    for (int i = 1; i <= n; ++i) ++c[t[i] = rk[id[i]]];
    for (int i = 1; i <= m; ++i) c[i] += c[i - 1];
    for (int i = n; i >= 1; --i) sa[c[t[i]]--] = id[i];
    memcpy(rrk, rk, sizeof(rk));
    p = 0;
    for (int i = 1; i <= n; ++i) rk[sa[i]] = cmp(sa[i], sa[i - 1], w) ? p : ++p;
  }
  for (int i = 1, j = 0; i <= n; ++i) {
    if (j) --j;
    while (a[i + j] == a[sa[rk[i] - 1] + j]) ++j;
    h[rk[i]] = j;
  }
}
int st[N][20], lg[N];
void getst() {
  for (int i = 1; i <= n; ++i) st[i][0] = h[i];
  for (int j = 1; j <= 17; ++j)
    for (int i = 1; i + (1 << j) - 1 <= n; ++i)
      st[i][j] = min(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);
  for (int i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1;
}
int ask(int l, int r) {
  int t = lg[r - l + 1];
  return min(st[l][t], st[r - (1 << t) + 1][t]);
}
struct yxl {
  set<int> s;
  long long val;
  void init() { s.insert(0), s.insert(n + 1); }
  void ins(int x) {
    if (s.count(x)) return;
    int l = *(--s.lower_bound(x));
    int r = *s.upper_bound(x);
    val += n - sa[x] + 1;
    if (l >= 1) val -= ask(l + 1, x);
    if (r <= n) val -= ask(x + 1, r);
    if (l >= 1 && r <= n) val += ask(l + 1, r);
    s.insert(x);
  }
} s[M];
long long res;
void dfs(int u) {
  for (int v : g[u]) {
    dfs(v);
    if (s[v].s.size() > s[u].s.size()) swap(s[u], s[v]);
    for (int x : s[v].s) s[u].ins(x);
  }
  res += s[u].val * (len[u] - len[link[u]]);
}
signed main() {
  scanf("%s", a + 1);
  n = strlen(a + 1);
  for (int i = 1; i <= n; ++i) extend(a[i] - 'a');
  getsa();
  getst();
  for (int i = 1; i <= tot; ++i) res += len[i] - len[link[i]];
  int now = 1;
  for (int i = 1; i <= n; ++i) now = ch[now][a[i] - 'a'];
  for (int i = 1; i <= tot; ++i)
    if (i != now) res += len[i] - len[link[i]];
  for (int i = 1; i <= tot; ++i) g[link[i]].push_back(i), s[i].init();
  now = 1;
  s[now].ins(rk[2]);
  for (int i = 1; i <= n - 2; ++i) {
    s[now = ch[now][a[i] - 'a']].ins(rk[i + 2]);
  }
  dfs(1);
  res += s[1].val;
  printf("%lld\n", res + 2);
  return 0;
}

```