#include <bits/stdc++.h>
const int maxn = 100005;
char s[maxn];
int sa[maxn], rank[maxn], hi[maxn];
int tmp[maxn], sa2[maxn], t[maxn];
void build(int n, int max) {
  for (int i = 1; i <= n; i++) rank[i] = s[i], sa2[i] = i;
  for (int i = 1; i <= n; i++) ++t[rank[i]];
  for (int i = 1; i <= max; i++) t[i] += t[i - 1];
  for (int i = n; i; i--) sa[t[rank[sa2[i]]]--] = sa2[i];
  std::fill(t + 1, t + max + 1, 0);
  int tot = rank[sa[1]] = 1;
  for (int i = 2; i <= n; i++)
    rank[sa[i]] = s[sa[i]] == s[sa[i - 1]] ? tot : ++tot;
  for (int m = 1; tot < n; m <<= 1) {
    int p = 0;
    for (int i = 1; i <= m; i++) sa2[++p] = n - m + i;
    for (int i = 1; i <= n; i++)
      if (sa[i] > m) sa2[++p] = sa[i] - m;
    for (int i = 1; i <= n; i++) ++t[rank[i]];
    for (int i = 1; i <= tot; i++) t[i] += t[i - 1];
    for (int i = n; i; i--) sa[t[rank[sa2[i]]]--] = sa2[i];
    std::fill(t + 1, t + tot + 1, 0);
    std::copy(rank, rank + n + 1, tmp);
    rank[sa[1]] = tot = 1;
    for (int i = 2; i <= n; i++)
      rank[sa[i]] = (tmp[sa[i]] == tmp[sa[i - 1]] and
                     tmp[sa[i] + m] == tmp[sa[i - 1] + m])
                        ? tot
                        : ++tot;
  }
  for (int i = 1; i <= n; i++) {
    int &k = hi[rank[i]] = std::max(0, hi[rank[i - 1]] - 1);
    while (s[i + k] == s[sa[rank[i] - 1] + k]) ++k;
  }
}
const int maxk = 26;
int ch[maxn << 1][maxk], len[maxn << 1], fa[maxn << 1], cp = 1;
std::vector<int> G[maxn << 1];
int insert(int pre, int x) {
  int now = ++cp;
  len[now] = len[pre] + 1;
  while (pre and !ch[pre][x]) {
    ch[pre][x] = now;
    pre = fa[pre];
  }
  if (pre) {
    int preto = ch[pre][x];
    if (len[preto] == len[pre] + 1)
      fa[now] = preto;
    else {
      int sp = ++cp;
      len[sp] = len[pre] + 1;
      fa[sp] = fa[preto];
      for (int i = 0; i < maxk; i++) ch[sp][i] = ch[preto][i];
      while (pre and ch[pre][x] == preto) {
        ch[pre][x] = sp;
        pre = fa[pre];
      }
      fa[now] = fa[preto] = sp;
    }
  } else
    fa[now] = 1;
  return now;
}
int st[maxn][20], hb[maxn];
void stinit(int n) {
  for (int i = n; i; i--) {
    st[i][0] = hi[i];
    for (int k = 1; i + (1 << k) - 1 <= n; k++)
      st[i][k] = std::min(st[i][k - 1], st[i + (1 << k >> 1)][k - 1]);
  }
  for (int i = 2; i <= n; i++) hb[i] = hb[i >> 1] + 1;
}
int stquery(int l, int r) {
  int k = hb[r - l + 1];
  return std::min(st[l][k], st[r - (1 << k) + 1][k]);
}
struct Set {
  std::set<int> set;
  long long val;
  void insert(int k, int n) {
    if (set.count(k)) return;
    int l = *(--set.lower_bound(k));
    int r = *set.upper_bound(k);
    val += n - sa[k] + 1;
    if (l >= 1) val -= stquery(l + 1, k);
    if (r <= n) val -= stquery(k + 1, r);
    if (l >= 1 and r <= n) val += stquery(l + 1, r);
    set.insert(k);
  }
  void init(int n) { set.insert(0), set.insert(n + 1); }
} set[maxn << 1];
long long ans;
void dfs(int u, int n) {
  for (int v : G[u]) {
    dfs(v, n);
    if (set[v].set.size() > set[u].set.size()) std::swap(set[u], set[v]);
    for (int k : set[v].set) set[u].insert(k, n);
  }
  ans += 1ll * (len[u] - len[fa[u]]) * set[u].val;
}
int main() {
  scanf("%s", s + 1);
  int n = int(strlen(s + 1));
  int sam = 1;
  for (int i = 1; i <= n; i++) sam = insert(sam, s[i] - 'a');
  build(n, 256);
  for (int i = 1; i <= cp; i++) set[i].init(n);
  stinit(n);
  sam = 1;
  set[sam].insert(rank[2], n);
  for (int i = 1; i <= n; i++) {
    sam = ch[sam][s[i] - 'a'];
    if (i + 2 <= n) set[sam].insert(rank[i + 2], n);
  }
  for (int i = 1; i <= cp; i++) ans += len[i] - len[fa[i]];
  for (int i = 2; i <= cp; i++) G[fa[i]].push_back(i);
  dfs(1, n);
  for (int i = 1; i <= cp; i++)
    if (i != sam) ans += len[i] - len[fa[i]];
  ans += set[1].val;
  ++ans;
  ++ans;
  printf("%lld\n", ans);
}

### Prompt

Create a solution in Cpp for 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>
const int maxn = 100005;
char s[maxn];
int sa[maxn], rank[maxn], hi[maxn];
int tmp[maxn], sa2[maxn], t[maxn];
void build(int n, int max) {
  for (int i = 1; i <= n; i++) rank[i] = s[i], sa2[i] = i;
  for (int i = 1; i <= n; i++) ++t[rank[i]];
  for (int i = 1; i <= max; i++) t[i] += t[i - 1];
  for (int i = n; i; i--) sa[t[rank[sa2[i]]]--] = sa2[i];
  std::fill(t + 1, t + max + 1, 0);
  int tot = rank[sa[1]] = 1;
  for (int i = 2; i <= n; i++)
    rank[sa[i]] = s[sa[i]] == s[sa[i - 1]] ? tot : ++tot;
  for (int m = 1; tot < n; m <<= 1) {
    int p = 0;
    for (int i = 1; i <= m; i++) sa2[++p] = n - m + i;
    for (int i = 1; i <= n; i++)
      if (sa[i] > m) sa2[++p] = sa[i] - m;
    for (int i = 1; i <= n; i++) ++t[rank[i]];
    for (int i = 1; i <= tot; i++) t[i] += t[i - 1];
    for (int i = n; i; i--) sa[t[rank[sa2[i]]]--] = sa2[i];
    std::fill(t + 1, t + tot + 1, 0);
    std::copy(rank, rank + n + 1, tmp);
    rank[sa[1]] = tot = 1;
    for (int i = 2; i <= n; i++)
      rank[sa[i]] = (tmp[sa[i]] == tmp[sa[i - 1]] and
                     tmp[sa[i] + m] == tmp[sa[i - 1] + m])
                        ? tot
                        : ++tot;
  }
  for (int i = 1; i <= n; i++) {
    int &k = hi[rank[i]] = std::max(0, hi[rank[i - 1]] - 1);
    while (s[i + k] == s[sa[rank[i] - 1] + k]) ++k;
  }
}
const int maxk = 26;
int ch[maxn << 1][maxk], len[maxn << 1], fa[maxn << 1], cp = 1;
std::vector<int> G[maxn << 1];
int insert(int pre, int x) {
  int now = ++cp;
  len[now] = len[pre] + 1;
  while (pre and !ch[pre][x]) {
    ch[pre][x] = now;
    pre = fa[pre];
  }
  if (pre) {
    int preto = ch[pre][x];
    if (len[preto] == len[pre] + 1)
      fa[now] = preto;
    else {
      int sp = ++cp;
      len[sp] = len[pre] + 1;
      fa[sp] = fa[preto];
      for (int i = 0; i < maxk; i++) ch[sp][i] = ch[preto][i];
      while (pre and ch[pre][x] == preto) {
        ch[pre][x] = sp;
        pre = fa[pre];
      }
      fa[now] = fa[preto] = sp;
    }
  } else
    fa[now] = 1;
  return now;
}
int st[maxn][20], hb[maxn];
void stinit(int n) {
  for (int i = n; i; i--) {
    st[i][0] = hi[i];
    for (int k = 1; i + (1 << k) - 1 <= n; k++)
      st[i][k] = std::min(st[i][k - 1], st[i + (1 << k >> 1)][k - 1]);
  }
  for (int i = 2; i <= n; i++) hb[i] = hb[i >> 1] + 1;
}
int stquery(int l, int r) {
  int k = hb[r - l + 1];
  return std::min(st[l][k], st[r - (1 << k) + 1][k]);
}
struct Set {
  std::set<int> set;
  long long val;
  void insert(int k, int n) {
    if (set.count(k)) return;
    int l = *(--set.lower_bound(k));
    int r = *set.upper_bound(k);
    val += n - sa[k] + 1;
    if (l >= 1) val -= stquery(l + 1, k);
    if (r <= n) val -= stquery(k + 1, r);
    if (l >= 1 and r <= n) val += stquery(l + 1, r);
    set.insert(k);
  }
  void init(int n) { set.insert(0), set.insert(n + 1); }
} set[maxn << 1];
long long ans;
void dfs(int u, int n) {
  for (int v : G[u]) {
    dfs(v, n);
    if (set[v].set.size() > set[u].set.size()) std::swap(set[u], set[v]);
    for (int k : set[v].set) set[u].insert(k, n);
  }
  ans += 1ll * (len[u] - len[fa[u]]) * set[u].val;
}
int main() {
  scanf("%s", s + 1);
  int n = int(strlen(s + 1));
  int sam = 1;
  for (int i = 1; i <= n; i++) sam = insert(sam, s[i] - 'a');
  build(n, 256);
  for (int i = 1; i <= cp; i++) set[i].init(n);
  stinit(n);
  sam = 1;
  set[sam].insert(rank[2], n);
  for (int i = 1; i <= n; i++) {
    sam = ch[sam][s[i] - 'a'];
    if (i + 2 <= n) set[sam].insert(rank[i + 2], n);
  }
  for (int i = 1; i <= cp; i++) ans += len[i] - len[fa[i]];
  for (int i = 2; i <= cp; i++) G[fa[i]].push_back(i);
  dfs(1, n);
  for (int i = 1; i <= cp; i++)
    if (i != sam) ans += len[i] - len[fa[i]];
  ans += set[1].val;
  ++ans;
  ++ans;
  printf("%lld\n", ans);
}

```