#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
int n, m, i, j, k, sa[N], rnk[N], h[N], tree[N * 4];
int ch[N * 2][26], fa[N * 2], len[N * 2], tot, last, pos[N * 2], vis[N * 2];
int head[N * 2], Next[N * 2], adj[N * 2];
long long ans, siz[N * 2];
char c[N];
struct asd {
  int x, y;
  bool operator<(const asd &a) const { return a.y > y; }
};
set<asd> d[N * 2];
struct str {
  int x, y;
};
void Build(int i, int l, int r) {
  if (l == r) {
    tree[i] = h[l];
    return;
  }
  int mid = l + r >> 1;
  Build(i << 1, l, mid);
  Build(i << 1 | 1, mid + 1, r);
  tree[i] = min(tree[i << 1], tree[i << 1 | 1]);
}
int Query(int i, int l, int r, int ll, int rr) {
  if (l >= ll && r <= rr) return tree[i];
  int mid = l + r >> 1, s = 1 << 30;
  if (mid >= ll) s = min(s, Query(i << 1, l, mid, ll, rr));
  if (mid < rr) s = min(s, Query(i << 1 | 1, mid + 1, r, ll, rr));
  return s;
}
void Insert(int c) {
  int p = last, nt = ++tot;
  len[tot] = len[last] + 1;
  last = nt;
  for (; p && !ch[p][c]; p = fa[p]) ch[p][c] = nt;
  if (!p)
    fa[nt] = 1;
  else {
    int q = ch[p][c];
    if (len[q] == len[p] + 1)
      fa[nt] = q;
    else {
      int nq = ++tot;
      memcpy(ch[nq], ch[q], sizeof(ch[nq]));
      fa[nq] = fa[q];
      fa[q] = fa[nt] = nq;
      len[nq] = len[p] + 1;
      for (; p && ch[p][c] == q; p = fa[p]) ch[p][c] = nq;
    }
  }
}
void Push(int u, int v) {
  Next[++k] = head[u];
  head[u] = k;
  adj[k] = v;
}
void dfs(int i) {
  int j;
  if (pos[i] && pos[i] < n - 1) {
    vis[i] = 1;
    siz[i] += n - pos[i] - 1;
    d[i].insert((asd){pos[i] + 2, rnk[pos[i] + 2]});
  } else if (pos[i] == n - 1)
    vis[i] = 1;
  if (i == 1) {
    siz[i] += n - 1;
    d[i].insert((asd){2, rnk[2]});
  }
  for (j = head[i]; j; j = Next[j]) {
    dfs(adj[j]);
    vis[i] |= vis[adj[j]];
    if (d[i].size() < d[adj[j]].size()) {
      swap(d[i], d[adj[j]]);
      siz[i] = siz[adj[j]];
    }
    for (auto it : d[adj[j]]) {
      auto tmp = d[i].lower_bound(it);
      auto t2 = tmp;
      if (tmp != d[i].end() && tmp != d[i].begin()) {
        --t2;
        siz[i] += Query(1, 1, n - 1, t2->y, tmp->y - 1);
      }
      if (tmp != d[i].end()) siz[i] -= Query(1, 1, n - 1, it.y, tmp->y - 1);
      if (tmp != d[i].begin()) {
        --tmp;
        siz[i] -= Query(1, 1, n - 1, tmp->y, it.y - 1);
      }
      d[i].insert(it);
      siz[i] += n - it.x + 1;
    }
  }
  ans += len[i] - len[fa[i]];
  if (vis[i]) ans += (len[i] - len[fa[i]]) * (siz[i] + 1);
}
struct node {
  int a, b, x;
} p[1000005];
bool cmp(node a, node b) {
  if (a.a == b.a) return a.b < b.b;
  return a.a < b.a;
}
int main() {
  scanf("%s", c + 1);
  n = strlen(c + 1);
  if (n == 1) {
    cout << 3;
    return 0;
  }
  for (i = 1; i <= n; i++) {
    p[i].a = c[i] - 'a' + 1;
    p[i].x = i;
  }
  sort(p + 1, p + 1 + n, cmp);
  for (i = 1; i <= n; i++)
    if (p[i].a == p[i - 1].a)
      sa[p[i].x] = sa[p[i - 1].x];
    else
      sa[p[i].x] = i;
  for (k = 1; k < n; k *= 2) {
    for (i = 1; i <= n - k; i++) p[i] = (node){sa[i], sa[i + k], i};
    for (i = n - k + 1; i <= n; i++) p[i] = (node){sa[i], 0, i};
    sort(p + 1, p + 1 + n, cmp);
    for (i = 1; i <= n; i++)
      if (p[i].a == p[i - 1].a && p[i].b == p[i - 1].b)
        sa[p[i].x] = sa[p[i - 1].x];
      else
        sa[p[i].x] = i;
  }
  for (i = 1; i <= n; ++i) rnk[sa[i]] = i;
  for (i = 1; i <= n; ++i) swap(sa[i], rnk[i]);
  h[1] = 0;
  last = 0;
  for (i = 2; i <= n; ++i) {
    for (j = 0; c[sa[i - 1] + j] == c[sa[i] + j]; ++j)
      ;
    h[i] = j;
    last = j;
  }
  for (i = 1; i < n; ++i) h[i] = h[i + 1];
  Build(1, 1, n - 1);
  last = tot = 1;
  for (i = 1; i <= n; ++i) {
    pos[tot + 1] = i;
    Insert(c[i] - 'a');
  }
  k = 0;
  for (i = 2; i <= tot; ++i) Push(fa[i], i);
  dfs(1);
  cout << ans + siz[1] + 2;
}

### Prompt

Please provide a Cpp coded solution to the problem described below:

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 = 200005;
int n, m, i, j, k, sa[N], rnk[N], h[N], tree[N * 4];
int ch[N * 2][26], fa[N * 2], len[N * 2], tot, last, pos[N * 2], vis[N * 2];
int head[N * 2], Next[N * 2], adj[N * 2];
long long ans, siz[N * 2];
char c[N];
struct asd {
  int x, y;
  bool operator<(const asd &a) const { return a.y > y; }
};
set<asd> d[N * 2];
struct str {
  int x, y;
};
void Build(int i, int l, int r) {
  if (l == r) {
    tree[i] = h[l];
    return;
  }
  int mid = l + r >> 1;
  Build(i << 1, l, mid);
  Build(i << 1 | 1, mid + 1, r);
  tree[i] = min(tree[i << 1], tree[i << 1 | 1]);
}
int Query(int i, int l, int r, int ll, int rr) {
  if (l >= ll && r <= rr) return tree[i];
  int mid = l + r >> 1, s = 1 << 30;
  if (mid >= ll) s = min(s, Query(i << 1, l, mid, ll, rr));
  if (mid < rr) s = min(s, Query(i << 1 | 1, mid + 1, r, ll, rr));
  return s;
}
void Insert(int c) {
  int p = last, nt = ++tot;
  len[tot] = len[last] + 1;
  last = nt;
  for (; p && !ch[p][c]; p = fa[p]) ch[p][c] = nt;
  if (!p)
    fa[nt] = 1;
  else {
    int q = ch[p][c];
    if (len[q] == len[p] + 1)
      fa[nt] = q;
    else {
      int nq = ++tot;
      memcpy(ch[nq], ch[q], sizeof(ch[nq]));
      fa[nq] = fa[q];
      fa[q] = fa[nt] = nq;
      len[nq] = len[p] + 1;
      for (; p && ch[p][c] == q; p = fa[p]) ch[p][c] = nq;
    }
  }
}
void Push(int u, int v) {
  Next[++k] = head[u];
  head[u] = k;
  adj[k] = v;
}
void dfs(int i) {
  int j;
  if (pos[i] && pos[i] < n - 1) {
    vis[i] = 1;
    siz[i] += n - pos[i] - 1;
    d[i].insert((asd){pos[i] + 2, rnk[pos[i] + 2]});
  } else if (pos[i] == n - 1)
    vis[i] = 1;
  if (i == 1) {
    siz[i] += n - 1;
    d[i].insert((asd){2, rnk[2]});
  }
  for (j = head[i]; j; j = Next[j]) {
    dfs(adj[j]);
    vis[i] |= vis[adj[j]];
    if (d[i].size() < d[adj[j]].size()) {
      swap(d[i], d[adj[j]]);
      siz[i] = siz[adj[j]];
    }
    for (auto it : d[adj[j]]) {
      auto tmp = d[i].lower_bound(it);
      auto t2 = tmp;
      if (tmp != d[i].end() && tmp != d[i].begin()) {
        --t2;
        siz[i] += Query(1, 1, n - 1, t2->y, tmp->y - 1);
      }
      if (tmp != d[i].end()) siz[i] -= Query(1, 1, n - 1, it.y, tmp->y - 1);
      if (tmp != d[i].begin()) {
        --tmp;
        siz[i] -= Query(1, 1, n - 1, tmp->y, it.y - 1);
      }
      d[i].insert(it);
      siz[i] += n - it.x + 1;
    }
  }
  ans += len[i] - len[fa[i]];
  if (vis[i]) ans += (len[i] - len[fa[i]]) * (siz[i] + 1);
}
struct node {
  int a, b, x;
} p[1000005];
bool cmp(node a, node b) {
  if (a.a == b.a) return a.b < b.b;
  return a.a < b.a;
}
int main() {
  scanf("%s", c + 1);
  n = strlen(c + 1);
  if (n == 1) {
    cout << 3;
    return 0;
  }
  for (i = 1; i <= n; i++) {
    p[i].a = c[i] - 'a' + 1;
    p[i].x = i;
  }
  sort(p + 1, p + 1 + n, cmp);
  for (i = 1; i <= n; i++)
    if (p[i].a == p[i - 1].a)
      sa[p[i].x] = sa[p[i - 1].x];
    else
      sa[p[i].x] = i;
  for (k = 1; k < n; k *= 2) {
    for (i = 1; i <= n - k; i++) p[i] = (node){sa[i], sa[i + k], i};
    for (i = n - k + 1; i <= n; i++) p[i] = (node){sa[i], 0, i};
    sort(p + 1, p + 1 + n, cmp);
    for (i = 1; i <= n; i++)
      if (p[i].a == p[i - 1].a && p[i].b == p[i - 1].b)
        sa[p[i].x] = sa[p[i - 1].x];
      else
        sa[p[i].x] = i;
  }
  for (i = 1; i <= n; ++i) rnk[sa[i]] = i;
  for (i = 1; i <= n; ++i) swap(sa[i], rnk[i]);
  h[1] = 0;
  last = 0;
  for (i = 2; i <= n; ++i) {
    for (j = 0; c[sa[i - 1] + j] == c[sa[i] + j]; ++j)
      ;
    h[i] = j;
    last = j;
  }
  for (i = 1; i < n; ++i) h[i] = h[i + 1];
  Build(1, 1, n - 1);
  last = tot = 1;
  for (i = 1; i <= n; ++i) {
    pos[tot + 1] = i;
    Insert(c[i] - 'a');
  }
  k = 0;
  for (i = 2; i <= tot; ++i) Push(fa[i], i);
  dfs(1);
  cout << ans + siz[1] + 2;
}

```