#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 100;
const int D = 18;
struct SAM {
  int next[N][26], fa[N], len[N], endpos[N];
  int root, tot, last;
  vector<int> son[N];
  int newnode(int l) {
    fa[tot] = -1;
    endpos[tot] = -1;
    for (int i = 0; i < 26; ++i) next[tot][i] = -1;
    len[tot++] = l;
    return tot - 1;
  }
  void init() {
    tot = 0;
    last = root = newnode(0);
  }
  void extend(int x, int ep) {
    int p = last;
    int cur = newnode(len[p] + 1);
    endpos[cur] = ep;
    while (p != -1 && next[p][x] == -1) {
      next[p][x] = cur;
      p = fa[p];
    }
    if (p == -1)
      fa[cur] = root;
    else {
      int q = next[p][x];
      if (len[q] == len[p] + 1)
        fa[cur] = q;
      else {
        int tmp = newnode(len[p] + 1);
        memcpy(next[tmp], next[q], sizeof(next[q]));
        fa[tmp] = fa[q];
        fa[q] = fa[cur] = tmp;
        while (p != -1 && next[p][x] == q) {
          next[p][x] = tmp;
          p = fa[p];
        }
      }
    }
    last = cur;
  }
  void build() {
    for (int i = 0; i < tot; ++i) son[i].clear();
    for (int i = 1; i < tot; ++i) son[fa[i]].push_back(i);
  }
} sam;
int lg2[N], xx[N], yy[N], c[N];
struct suffix_array {
  int str[N], sa[N], rank[N], height[N];
  int rmq[D][N];
  bool cmp(int* r, int a, int b, int l) {
    return r[a] == r[b] && r[a + l] == r[b + l];
  }
  void da(int n, int m) {
    n++;
    int i, j, p, *x = xx, *y = yy;
    for (i = 0; i < m; ++i) c[i] = 0;
    for (i = 0; i < n; ++i) c[x[i] = str[i]]++;
    for (i = 1; i < m; ++i) c[i] += c[i - 1];
    for (i = n - 1; i >= 0; --i) sa[--c[x[i]]] = i;
    for (j = 1; j < n; j <<= 1) {
      p = 0;
      for (i = n - j; i < n; ++i) y[p++] = i;
      for (i = 0; i < n; ++i)
        if (sa[i] >= j) y[p++] = sa[i] - j;
      for (i = 0; i < m; ++i) c[i] = 0;
      for (i = 0; i < n; ++i) c[x[y[i]]]++;
      for (i = 1; i < m; ++i) c[i] += c[i - 1];
      for (i = n - 1; i >= 0; --i) sa[--c[x[y[i]]]] = y[i];
      swap(x, y);
      p = 1;
      x[sa[0]] = 0;
      for (i = 1; i < n; ++i)
        x[sa[i]] = cmp(y, sa[i - 1], sa[i], j) ? p - 1 : p++;
      if (p >= n) break;
      m = p;
    }
    int k = 0;
    n--;
    for (i = 0; i <= n; ++i) rank[sa[i]] = i;
    for (i = 0; i < n; ++i) {
      if (k) k--;
      j = sa[rank[i] - 1];
      while (str[i + k] == str[j + k]) ++k;
      height[rank[i]] = k;
    }
  }
  void initlcp(int n) {
    for (int i = 1; i <= n; ++i) rmq[0][i] = height[i];
    for (int k = 1; k <= lg2[n]; ++k)
      for (int i = 1; i + (1 << k) - 1 <= n; ++i)
        rmq[k][i] = min(rmq[k - 1][i], rmq[k - 1][i + (1 << (k - 1))]);
  }
  int lcp(int a, int b) {
    a = rank[a];
    b = rank[b];
    if (a > b) swap(a, b);
    a += 1;
    int d = lg2[b - a + 1];
    return min(rmq[d][a], rmq[d][b - (1 << d) + 1]);
  }
} sa;
int n;
char s[N];
struct cmp {
  bool operator()(const int& a, const int& b) const {
    return sa.rank[a] < sa.rank[b];
  }
};
struct DATA {
  set<int, cmp> st;
  long long val = 1;
  void clear() {
    st.clear();
    val = 1;
  }
  int size() { return st.size(); }
  void insert(int x) {
    set<int, cmp>::iterator l, r;
    st.insert(x);
    l = r = st.lower_bound(x);
    if (l != st.begin()) l--;
    r++;
    val += n - x;
    if (*l != x && r != st.end()) val += sa.lcp(*l, *r);
    if (*l != x) val -= sa.lcp(*l, x);
    if (r != st.end()) val -= sa.lcp(*r, x);
  }
} Data;
long long ans = 0;
int siz[N], son[N];
void dfs1(int u) {
  siz[u] = 1;
  son[u] = -1;
  for (auto v : sam.son[u]) {
    dfs1(v);
    siz[u] += siz[v];
    if (son[u] == -1 || siz[son[u]] < siz[v]) son[u] = v;
  }
}
void dfs2(int u) {
  if (~sam.endpos[u]) Data.insert(sam.endpos[u]);
  for (auto v : sam.son[u]) dfs2(v);
}
void dfs3(int u, bool flg) {
  for (auto v : sam.son[u])
    if (v != son[u]) dfs3(v, true);
  if (~son[u]) dfs3(son[u], false);
  if (~sam.endpos[u]) Data.insert(sam.endpos[u]);
  for (auto v : sam.son[u])
    if (v != son[u]) dfs2(v);
  if (Data.size() == 0)
    ans += sam.len[u] - sam.len[sam.fa[u]];
  else if (u)
    ans += (sam.len[u] - sam.len[sam.fa[u]]) * (Data.val + 1);
  else
    ans += Data.val;
  if (flg) Data.clear();
}
int main() {
  scanf("%s", s);
  n = strlen(s);
  sam.init();
  sam.endpos[0] = 1;
  for (int i = 0; i < n; ++i) sam.extend(s[i] - 'a', i + 2 <= n ? i + 2 : -1);
  sam.build();
  lg2[0] = -1;
  for (int i = 1; i <= n; ++i)
    lg2[i] = i & (i - 1) ? lg2[i - 1] : lg2[i - 1] + 1;
  for (int i = 0; i < n; ++i) sa.str[i] = s[i] - 'a' + 1;
  sa.str[n] = 0;
  sa.da(n, 27);
  sa.initlcp(n);
  dfs1(sam.root);
  dfs3(sam.root, true);
  printf("%lld\n", ans + 1);
}

### 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 = 2e5 + 100;
const int D = 18;
struct SAM {
  int next[N][26], fa[N], len[N], endpos[N];
  int root, tot, last;
  vector<int> son[N];
  int newnode(int l) {
    fa[tot] = -1;
    endpos[tot] = -1;
    for (int i = 0; i < 26; ++i) next[tot][i] = -1;
    len[tot++] = l;
    return tot - 1;
  }
  void init() {
    tot = 0;
    last = root = newnode(0);
  }
  void extend(int x, int ep) {
    int p = last;
    int cur = newnode(len[p] + 1);
    endpos[cur] = ep;
    while (p != -1 && next[p][x] == -1) {
      next[p][x] = cur;
      p = fa[p];
    }
    if (p == -1)
      fa[cur] = root;
    else {
      int q = next[p][x];
      if (len[q] == len[p] + 1)
        fa[cur] = q;
      else {
        int tmp = newnode(len[p] + 1);
        memcpy(next[tmp], next[q], sizeof(next[q]));
        fa[tmp] = fa[q];
        fa[q] = fa[cur] = tmp;
        while (p != -1 && next[p][x] == q) {
          next[p][x] = tmp;
          p = fa[p];
        }
      }
    }
    last = cur;
  }
  void build() {
    for (int i = 0; i < tot; ++i) son[i].clear();
    for (int i = 1; i < tot; ++i) son[fa[i]].push_back(i);
  }
} sam;
int lg2[N], xx[N], yy[N], c[N];
struct suffix_array {
  int str[N], sa[N], rank[N], height[N];
  int rmq[D][N];
  bool cmp(int* r, int a, int b, int l) {
    return r[a] == r[b] && r[a + l] == r[b + l];
  }
  void da(int n, int m) {
    n++;
    int i, j, p, *x = xx, *y = yy;
    for (i = 0; i < m; ++i) c[i] = 0;
    for (i = 0; i < n; ++i) c[x[i] = str[i]]++;
    for (i = 1; i < m; ++i) c[i] += c[i - 1];
    for (i = n - 1; i >= 0; --i) sa[--c[x[i]]] = i;
    for (j = 1; j < n; j <<= 1) {
      p = 0;
      for (i = n - j; i < n; ++i) y[p++] = i;
      for (i = 0; i < n; ++i)
        if (sa[i] >= j) y[p++] = sa[i] - j;
      for (i = 0; i < m; ++i) c[i] = 0;
      for (i = 0; i < n; ++i) c[x[y[i]]]++;
      for (i = 1; i < m; ++i) c[i] += c[i - 1];
      for (i = n - 1; i >= 0; --i) sa[--c[x[y[i]]]] = y[i];
      swap(x, y);
      p = 1;
      x[sa[0]] = 0;
      for (i = 1; i < n; ++i)
        x[sa[i]] = cmp(y, sa[i - 1], sa[i], j) ? p - 1 : p++;
      if (p >= n) break;
      m = p;
    }
    int k = 0;
    n--;
    for (i = 0; i <= n; ++i) rank[sa[i]] = i;
    for (i = 0; i < n; ++i) {
      if (k) k--;
      j = sa[rank[i] - 1];
      while (str[i + k] == str[j + k]) ++k;
      height[rank[i]] = k;
    }
  }
  void initlcp(int n) {
    for (int i = 1; i <= n; ++i) rmq[0][i] = height[i];
    for (int k = 1; k <= lg2[n]; ++k)
      for (int i = 1; i + (1 << k) - 1 <= n; ++i)
        rmq[k][i] = min(rmq[k - 1][i], rmq[k - 1][i + (1 << (k - 1))]);
  }
  int lcp(int a, int b) {
    a = rank[a];
    b = rank[b];
    if (a > b) swap(a, b);
    a += 1;
    int d = lg2[b - a + 1];
    return min(rmq[d][a], rmq[d][b - (1 << d) + 1]);
  }
} sa;
int n;
char s[N];
struct cmp {
  bool operator()(const int& a, const int& b) const {
    return sa.rank[a] < sa.rank[b];
  }
};
struct DATA {
  set<int, cmp> st;
  long long val = 1;
  void clear() {
    st.clear();
    val = 1;
  }
  int size() { return st.size(); }
  void insert(int x) {
    set<int, cmp>::iterator l, r;
    st.insert(x);
    l = r = st.lower_bound(x);
    if (l != st.begin()) l--;
    r++;
    val += n - x;
    if (*l != x && r != st.end()) val += sa.lcp(*l, *r);
    if (*l != x) val -= sa.lcp(*l, x);
    if (r != st.end()) val -= sa.lcp(*r, x);
  }
} Data;
long long ans = 0;
int siz[N], son[N];
void dfs1(int u) {
  siz[u] = 1;
  son[u] = -1;
  for (auto v : sam.son[u]) {
    dfs1(v);
    siz[u] += siz[v];
    if (son[u] == -1 || siz[son[u]] < siz[v]) son[u] = v;
  }
}
void dfs2(int u) {
  if (~sam.endpos[u]) Data.insert(sam.endpos[u]);
  for (auto v : sam.son[u]) dfs2(v);
}
void dfs3(int u, bool flg) {
  for (auto v : sam.son[u])
    if (v != son[u]) dfs3(v, true);
  if (~son[u]) dfs3(son[u], false);
  if (~sam.endpos[u]) Data.insert(sam.endpos[u]);
  for (auto v : sam.son[u])
    if (v != son[u]) dfs2(v);
  if (Data.size() == 0)
    ans += sam.len[u] - sam.len[sam.fa[u]];
  else if (u)
    ans += (sam.len[u] - sam.len[sam.fa[u]]) * (Data.val + 1);
  else
    ans += Data.val;
  if (flg) Data.clear();
}
int main() {
  scanf("%s", s);
  n = strlen(s);
  sam.init();
  sam.endpos[0] = 1;
  for (int i = 0; i < n; ++i) sam.extend(s[i] - 'a', i + 2 <= n ? i + 2 : -1);
  sam.build();
  lg2[0] = -1;
  for (int i = 1; i <= n; ++i)
    lg2[i] = i & (i - 1) ? lg2[i - 1] : lg2[i - 1] + 1;
  for (int i = 0; i < n; ++i) sa.str[i] = s[i] - 'a' + 1;
  sa.str[n] = 0;
  sa.da(n, 27);
  sa.initlcp(n);
  dfs1(sam.root);
  dfs3(sam.root, true);
  printf("%lld\n", ans + 1);
}

```