#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
int Mod(int x) { return x >= mod ? x - mod : x; }
long long read() {
  long long x = 0;
  int f = 1;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) x = x * 10 + (ch ^ 48);
  return x * f;
}
void print(long long x) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) print(x / 10);
  putchar(x % 10 + '0');
}
const int N = 200010;
int n;
long long ans;
struct Suffix_Array {
  char s[N];
  int m;
  int rnk[N], sa[N], tp[N], t[N], h[N];
  void qsort() {
    for (int i = 0; i <= m; i++) t[i] = 0;
    for (int i = 1; i <= n; i++) t[rnk[i]]++;
    for (int i = 1; i <= m; i++) t[i] += t[i - 1];
    for (int i = n; i; i--) sa[t[rnk[tp[i]]]--] = tp[i];
  }
  void suffix_sort() {
    m = 122;
    for (int i = 1; i <= n; i++) rnk[i] = s[i] - 'a' + 1, tp[i] = i;
    qsort();
    for (int w = 1, p = 0; p < n; m = p, w <<= 1) {
      p = 0;
      for (int i = 1; i <= w; i++) tp[++p] = n - w + i;
      for (int i = 1; i <= n; i++)
        if (sa[i] > w) tp[++p] = sa[i] - w;
      qsort();
      swap(tp, rnk);
      rnk[sa[1]] = p = 1;
      for (int i = 2; i <= n; i++)
        rnk[sa[i]] =
            (tp[sa[i - 1]] == tp[sa[i]] && tp[sa[i - 1] + w] == tp[sa[i] + w])
                ? p
                : ++p;
    }
  }
  void get_h() {
    int k = 0;
    for (int i = 1; i <= n; i++) {
      if (k) k--;
      int j = sa[rnk[i] - 1];
      while (s[i + k] == s[j + k]) k++;
      h[rnk[i]] = k;
    }
  }
  int st[N][18], lg[N];
  void get_st() {
    for (int i = 1; i <= n; i++) st[i][0] = h[i];
    for (int j = 1; j < 18; 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]);
  }
  int query(int l, int r) {
    l++;
    int t = lg[r - l + 1];
    return min(st[l][t], st[r - (1 << t) + 1][t]);
  }
  void build() {
    lg[1] = 0;
    for (int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;
    suffix_sort(), get_h(), get_st();
  }
} SA;
struct Set {
  set<int> s;
  long long val;
  void init() { s.insert(0), s.insert(n + 1); }
  void insert(int k) {
    if (s.count(k)) return;
    int l = *(--s.lower_bound(k)), r = *s.upper_bound(k);
    val += n - SA.sa[k] + 1;
    if (l >= 1) val -= SA.query(l, k);
    if (r <= n) val -= SA.query(k, r);
    if (l >= 1 && r <= n) val += SA.query(l, r);
    s.insert(k);
  }
} S[N];
struct SAM {
  struct state {
    int len, link, nxt[26];
    int& operator[](int i) { return nxt[i]; }
  } st[N];
  int tot, lst;
  SAM() { lst = tot = 1; }
  void insert(char c) {
    int cur = ++tot;
    st[cur].len = st[lst].len + 1;
    int p = lst;
    lst = cur;
    for (; p && !st[p].nxt[c]; p = st[p].link) st[p].nxt[c] = cur;
    if (!p)
      st[cur].link = 1;
    else {
      int q = st[p].nxt[c];
      if (st[q].len == st[p].len + 1)
        st[cur].link = q;
      else {
        int clone = ++tot;
        st[clone] = st[q];
        st[clone].len = st[p].len + 1;
        for (; p && st[p].nxt[c] == q; p = st[p].link) st[p].nxt[c] = clone;
        st[q].link = st[cur].link = clone;
      }
    }
  }
  static const int M = N >> 1;
  ;
  struct edge {
    int nxt, to;
    long long w;
  } e[M << 1];
  int head[N], cnt = 1;
  void add(int u, int v, long long w = 0) {
    e[++cnt].w = w, e[cnt].to = v, e[cnt].nxt = head[u];
    head[u] = cnt;
  }
  void add_edge(int u, int v, long long w = 0) {
    add(u, v, w), add(v, u, w * 1);
  };
  void build() {
    for (int i = 2; i <= tot; i++) add(st[i].link, i);
    for (int i = 1; i <= tot; i++) S[i].init();
  }
  void dfs(int u) {
    for (int i = head[u]; i; i = e[i].nxt) {
      int v = e[i].to;
      dfs(v);
      if (S[v].s.size() > S[u].s.size()) swap(S[u], S[v]);
      for (int k : S[v].s) S[u].insert(k);
    }
    ans += (st[u].len - st[st[u].link].len) * S[u].val;
  }
  void get_ans() {
    for (int i = 1; i <= tot; i++)
      ans += (st[i].len - st[st[i].link].len) * (2 - (i == lst));
    dfs(1);
    ans += S[1].val + 2;
  }
} SAM;
char c[N];
int main() {
  scanf("%s", c + 1), n = strlen(c + 1);
  for (int i = 1; i <= n; i++) SA.s[i] = c[i], SAM.insert(c[i] - 'a');
  SA.build(), SAM.build();
  int u = 1;
  S[1].insert(SA.rnk[2]);
  for (int i = 1; i <= n; i++) {
    u = SAM.st[u][c[i] - 'a'];
    if (i + 2 <= n) S[u].insert(SA.rnk[i + 2]);
  }
  SAM.get_ans();
  print(ans), putchar('\n');
  return 0;
}

### Prompt

Generate a CPP solution 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;
const int mod = 998244353;
int Mod(int x) { return x >= mod ? x - mod : x; }
long long read() {
  long long x = 0;
  int f = 1;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) x = x * 10 + (ch ^ 48);
  return x * f;
}
void print(long long x) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) print(x / 10);
  putchar(x % 10 + '0');
}
const int N = 200010;
int n;
long long ans;
struct Suffix_Array {
  char s[N];
  int m;
  int rnk[N], sa[N], tp[N], t[N], h[N];
  void qsort() {
    for (int i = 0; i <= m; i++) t[i] = 0;
    for (int i = 1; i <= n; i++) t[rnk[i]]++;
    for (int i = 1; i <= m; i++) t[i] += t[i - 1];
    for (int i = n; i; i--) sa[t[rnk[tp[i]]]--] = tp[i];
  }
  void suffix_sort() {
    m = 122;
    for (int i = 1; i <= n; i++) rnk[i] = s[i] - 'a' + 1, tp[i] = i;
    qsort();
    for (int w = 1, p = 0; p < n; m = p, w <<= 1) {
      p = 0;
      for (int i = 1; i <= w; i++) tp[++p] = n - w + i;
      for (int i = 1; i <= n; i++)
        if (sa[i] > w) tp[++p] = sa[i] - w;
      qsort();
      swap(tp, rnk);
      rnk[sa[1]] = p = 1;
      for (int i = 2; i <= n; i++)
        rnk[sa[i]] =
            (tp[sa[i - 1]] == tp[sa[i]] && tp[sa[i - 1] + w] == tp[sa[i] + w])
                ? p
                : ++p;
    }
  }
  void get_h() {
    int k = 0;
    for (int i = 1; i <= n; i++) {
      if (k) k--;
      int j = sa[rnk[i] - 1];
      while (s[i + k] == s[j + k]) k++;
      h[rnk[i]] = k;
    }
  }
  int st[N][18], lg[N];
  void get_st() {
    for (int i = 1; i <= n; i++) st[i][0] = h[i];
    for (int j = 1; j < 18; 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]);
  }
  int query(int l, int r) {
    l++;
    int t = lg[r - l + 1];
    return min(st[l][t], st[r - (1 << t) + 1][t]);
  }
  void build() {
    lg[1] = 0;
    for (int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;
    suffix_sort(), get_h(), get_st();
  }
} SA;
struct Set {
  set<int> s;
  long long val;
  void init() { s.insert(0), s.insert(n + 1); }
  void insert(int k) {
    if (s.count(k)) return;
    int l = *(--s.lower_bound(k)), r = *s.upper_bound(k);
    val += n - SA.sa[k] + 1;
    if (l >= 1) val -= SA.query(l, k);
    if (r <= n) val -= SA.query(k, r);
    if (l >= 1 && r <= n) val += SA.query(l, r);
    s.insert(k);
  }
} S[N];
struct SAM {
  struct state {
    int len, link, nxt[26];
    int& operator[](int i) { return nxt[i]; }
  } st[N];
  int tot, lst;
  SAM() { lst = tot = 1; }
  void insert(char c) {
    int cur = ++tot;
    st[cur].len = st[lst].len + 1;
    int p = lst;
    lst = cur;
    for (; p && !st[p].nxt[c]; p = st[p].link) st[p].nxt[c] = cur;
    if (!p)
      st[cur].link = 1;
    else {
      int q = st[p].nxt[c];
      if (st[q].len == st[p].len + 1)
        st[cur].link = q;
      else {
        int clone = ++tot;
        st[clone] = st[q];
        st[clone].len = st[p].len + 1;
        for (; p && st[p].nxt[c] == q; p = st[p].link) st[p].nxt[c] = clone;
        st[q].link = st[cur].link = clone;
      }
    }
  }
  static const int M = N >> 1;
  ;
  struct edge {
    int nxt, to;
    long long w;
  } e[M << 1];
  int head[N], cnt = 1;
  void add(int u, int v, long long w = 0) {
    e[++cnt].w = w, e[cnt].to = v, e[cnt].nxt = head[u];
    head[u] = cnt;
  }
  void add_edge(int u, int v, long long w = 0) {
    add(u, v, w), add(v, u, w * 1);
  };
  void build() {
    for (int i = 2; i <= tot; i++) add(st[i].link, i);
    for (int i = 1; i <= tot; i++) S[i].init();
  }
  void dfs(int u) {
    for (int i = head[u]; i; i = e[i].nxt) {
      int v = e[i].to;
      dfs(v);
      if (S[v].s.size() > S[u].s.size()) swap(S[u], S[v]);
      for (int k : S[v].s) S[u].insert(k);
    }
    ans += (st[u].len - st[st[u].link].len) * S[u].val;
  }
  void get_ans() {
    for (int i = 1; i <= tot; i++)
      ans += (st[i].len - st[st[i].link].len) * (2 - (i == lst));
    dfs(1);
    ans += S[1].val + 2;
  }
} SAM;
char c[N];
int main() {
  scanf("%s", c + 1), n = strlen(c + 1);
  for (int i = 1; i <= n; i++) SA.s[i] = c[i], SAM.insert(c[i] - 'a');
  SA.build(), SAM.build();
  int u = 1;
  S[1].insert(SA.rnk[2]);
  for (int i = 1; i <= n; i++) {
    u = SAM.st[u][c[i] - 'a'];
    if (i + 2 <= n) S[u].insert(SA.rnk[i + 2]);
  }
  SAM.get_ans();
  print(ans), putchar('\n');
  return 0;
}

```