#include <bits/stdc++.h>
using namespace std;
const int oo = 2139063143;
const int N = 200100;
const int P = 1000000007;
const double eps = 1e-7;
template <typename T>
inline void sc(T &x) {
  x = 0;
  static int p;
  p = 1;
  static char c;
  c = getchar();
  while (!isdigit(c)) {
    if (c == '-') p = -1;
    c = getchar();
  }
  while (isdigit(c)) {
    x = (x << 1) + (x << 3) + (c - 48);
    c = getchar();
  }
  x *= p;
}
template <typename T>
inline void print(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}
template <typename T>
inline void pr(T x) {
  print(x), putchar('\n');
}
template <typename T1, typename T2>
void chkmax(T1 &A, T2 B) {
  A = A >= B ? A : B;
}
template <typename T1, typename T2>
void chkmin(T1 &A, T2 B) {
  A = A <= B ? A : B;
}
int n;
struct SA {
  int sa[N], rk[N], hei[N], cnt[N], tmp1[N], tmp2[N];
  int st[N][19], bit[N];
  void init() {
    bit[0] = -1;
    for (int i = 1; i <= n; i++) bit[i] = bit[i >> 1] + 1;
    for (int i = 1; i <= n; i++) st[i][0] = hei[i];
    for (int j = 1; j <= bit[n]; j++)
      for (int i = 1; i <= n; i++)
        st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
  }
  void build(char *s) {
    int m = 0, *x = tmp1, *y = tmp2;
    for (int i = 1; i <= n; i++) chkmax(m, x[i] = s[i]);
    for (int i = 1; i <= n; i++) ++cnt[x[i]];
    for (int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
    for (int i = n; i >= 1; i--) sa[cnt[x[i]]--] = i;
    for (int len = 1; len <= n; len <<= 1) {
      int z = 0;
      for (int i = n - len + 1; i <= n; i++) y[++z] = i;
      for (int i = 1; i <= n; i++)
        if (sa[i] > len) y[++z] = sa[i] - len;
      memset(cnt, 0, sizeof(int) * (m + 1));
      for (int i = 1; i <= n; i++) ++cnt[x[y[i]]];
      for (int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
      for (int i = n; i >= 1; i--) sa[cnt[x[y[i]]]--] = y[i];
      swap(x, y);
      m = x[sa[1]] = 1;
      for (int i = 2; i <= n; i++)
        if (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + len] == y[sa[i - 1] + len])
          x[sa[i]] = m;
        else
          x[sa[i]] = ++m;
      if (m == n) break;
    }
    for (int i = 1; i <= n; i++) rk[sa[i]] = i;
    for (int i = 1, k = 0; i <= n; i++) {
      if (k) --k;
      while (s[i + k] == s[sa[rk[i] - 1] + k]) ++k;
      hei[rk[i]] = k;
    }
    init();
  }
  int lcp(int x, int y) {
    if (x > y) swap(x, y);
    ++x;
    int k = bit[y - x + 1];
    return min(st[x][k], st[y - (1 << k) + 1][k]);
  }
} sa;
struct SAM {
  struct DATASAM {
    int fa, son[26], len, siz;
    set<int> s;
    long long sum;
  } t[N << 1];
  int tot = 1, pre = 1;
  void addchar(int c) {
    int f = pre, p = ++tot;
    pre = p;
    t[p].len = t[f].len + 1, t[p].siz = 1;
    while (f && !t[f].son[c]) t[f].son[c] = p, f = t[f].fa;
    if (!f) return t[p].fa = 1, void();
    int x = t[f].son[c];
    if (t[x].len == t[f].len + 1) return t[p].fa = x, void();
    int y = ++tot;
    t[y].len = t[f].len + 1;
    t[y].fa = t[x].fa, t[x].fa = t[p].fa = y;
    memcpy(t[y].son, t[x].son, sizeof(t[y].son));
    while (f && t[f].son[c] == x) t[f].son[c] = y, f = t[f].fa;
  }
  void build(char *s, int n) {
    for (int i = 1; i <= n; i++) addchar(s[i] - 'a');
  }
  void merge(int x, int y) {
    if (t[x].s.size() > t[y].s.size())
      swap(t[x].s, t[y].s), swap(t[x].sum, t[y].sum);
    for (set<int>::iterator it = t[x].s.begin(), it1, it2; it != t[x].s.end();
         ++it) {
      int pos = *it, g = 0;
      it1 = t[y].s.lower_bound(pos);
      if (it1 != t[y].s.begin()) {
        --it1;
        chkmax(g, sa.lcp(*it1, pos));
      }
      it2 = t[y].s.upper_bound(pos);
      if (it2 != t[y].s.end()) {
        chkmax(g, sa.lcp(*it2, pos));
      }
      t[y].sum += n - sa.sa[pos] + 1 - g, t[y].s.insert(pos);
    }
    t[x].s.clear();
  }
  int deg[N];
  long long solve(char *s) {
    for (int i = 1, p = 1; i <= n - 2; i++)
      p = t[p].son[s[i] - 'a'], t[p].s.insert(sa.rk[i + 2]),
      t[p].sum = n - i - 1;
    memset(deg, 0, sizeof(int) * (tot + 1));
    queue<int> q;
    for (int i = 1; i <= tot; i++) ++deg[t[i].fa];
    for (int i = 1; i <= tot; i++)
      if (!deg[i]) q.push(i);
    long long ans = 0;
    while (q.size()) {
      int u = q.front(), f = t[u].fa;
      q.pop();
      ans += t[u].sum * (t[u].len - t[t[u].fa].len);
      merge(u, f);
      if (!--deg[f]) q.push(f);
    }
    return ans;
  }
  long long get() {
    memset(deg, 0, sizeof(int) * (tot + 1));
    for (int i = 1; i <= tot; i++) ++deg[t[i].fa];
    queue<int> q;
    for (int i = 1; i <= tot; i++)
      if (!deg[i]) q.push(i);
    long long ans = 0;
    while (q.size()) {
      int u = q.front(), f = t[u].fa;
      q.pop();
      ans += t[u].len - t[t[u].fa].len;
      t[f].siz += t[u].siz;
      if (!--deg[f]) q.push(f);
    }
    return ans;
  }
  void clear() {
    for (int i = 1; i <= tot; i++) {
      t[i].fa = t[i].len = t[i].siz = 0;
      t[i].sum = 0;
      t[i].s.clear();
      memset(t[i].son, 0, sizeof(t[i].son));
    }
    tot = pre = 1;
  }
} sam;
char s[N];
int main() {
  scanf("%s", s + 1);
  n = strlen(s + 1);
  long long ans = 0;
  sam.build(s + 1, n - 1), ans += sam.get(), sam.clear();
  sam.build(s, n - 1), ans += sam.get(), sam.clear();
  sam.build(s, n);
  ans += sam.get();
  sa.build(s);
  ans += sam.solve(s);
  pr(ans + 2);
  return 0;
}

### Prompt

Construct a cpp code solution to the problem outlined:

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 oo = 2139063143;
const int N = 200100;
const int P = 1000000007;
const double eps = 1e-7;
template <typename T>
inline void sc(T &x) {
  x = 0;
  static int p;
  p = 1;
  static char c;
  c = getchar();
  while (!isdigit(c)) {
    if (c == '-') p = -1;
    c = getchar();
  }
  while (isdigit(c)) {
    x = (x << 1) + (x << 3) + (c - 48);
    c = getchar();
  }
  x *= p;
}
template <typename T>
inline void print(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}
template <typename T>
inline void pr(T x) {
  print(x), putchar('\n');
}
template <typename T1, typename T2>
void chkmax(T1 &A, T2 B) {
  A = A >= B ? A : B;
}
template <typename T1, typename T2>
void chkmin(T1 &A, T2 B) {
  A = A <= B ? A : B;
}
int n;
struct SA {
  int sa[N], rk[N], hei[N], cnt[N], tmp1[N], tmp2[N];
  int st[N][19], bit[N];
  void init() {
    bit[0] = -1;
    for (int i = 1; i <= n; i++) bit[i] = bit[i >> 1] + 1;
    for (int i = 1; i <= n; i++) st[i][0] = hei[i];
    for (int j = 1; j <= bit[n]; j++)
      for (int i = 1; i <= n; i++)
        st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
  }
  void build(char *s) {
    int m = 0, *x = tmp1, *y = tmp2;
    for (int i = 1; i <= n; i++) chkmax(m, x[i] = s[i]);
    for (int i = 1; i <= n; i++) ++cnt[x[i]];
    for (int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
    for (int i = n; i >= 1; i--) sa[cnt[x[i]]--] = i;
    for (int len = 1; len <= n; len <<= 1) {
      int z = 0;
      for (int i = n - len + 1; i <= n; i++) y[++z] = i;
      for (int i = 1; i <= n; i++)
        if (sa[i] > len) y[++z] = sa[i] - len;
      memset(cnt, 0, sizeof(int) * (m + 1));
      for (int i = 1; i <= n; i++) ++cnt[x[y[i]]];
      for (int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
      for (int i = n; i >= 1; i--) sa[cnt[x[y[i]]]--] = y[i];
      swap(x, y);
      m = x[sa[1]] = 1;
      for (int i = 2; i <= n; i++)
        if (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + len] == y[sa[i - 1] + len])
          x[sa[i]] = m;
        else
          x[sa[i]] = ++m;
      if (m == n) break;
    }
    for (int i = 1; i <= n; i++) rk[sa[i]] = i;
    for (int i = 1, k = 0; i <= n; i++) {
      if (k) --k;
      while (s[i + k] == s[sa[rk[i] - 1] + k]) ++k;
      hei[rk[i]] = k;
    }
    init();
  }
  int lcp(int x, int y) {
    if (x > y) swap(x, y);
    ++x;
    int k = bit[y - x + 1];
    return min(st[x][k], st[y - (1 << k) + 1][k]);
  }
} sa;
struct SAM {
  struct DATASAM {
    int fa, son[26], len, siz;
    set<int> s;
    long long sum;
  } t[N << 1];
  int tot = 1, pre = 1;
  void addchar(int c) {
    int f = pre, p = ++tot;
    pre = p;
    t[p].len = t[f].len + 1, t[p].siz = 1;
    while (f && !t[f].son[c]) t[f].son[c] = p, f = t[f].fa;
    if (!f) return t[p].fa = 1, void();
    int x = t[f].son[c];
    if (t[x].len == t[f].len + 1) return t[p].fa = x, void();
    int y = ++tot;
    t[y].len = t[f].len + 1;
    t[y].fa = t[x].fa, t[x].fa = t[p].fa = y;
    memcpy(t[y].son, t[x].son, sizeof(t[y].son));
    while (f && t[f].son[c] == x) t[f].son[c] = y, f = t[f].fa;
  }
  void build(char *s, int n) {
    for (int i = 1; i <= n; i++) addchar(s[i] - 'a');
  }
  void merge(int x, int y) {
    if (t[x].s.size() > t[y].s.size())
      swap(t[x].s, t[y].s), swap(t[x].sum, t[y].sum);
    for (set<int>::iterator it = t[x].s.begin(), it1, it2; it != t[x].s.end();
         ++it) {
      int pos = *it, g = 0;
      it1 = t[y].s.lower_bound(pos);
      if (it1 != t[y].s.begin()) {
        --it1;
        chkmax(g, sa.lcp(*it1, pos));
      }
      it2 = t[y].s.upper_bound(pos);
      if (it2 != t[y].s.end()) {
        chkmax(g, sa.lcp(*it2, pos));
      }
      t[y].sum += n - sa.sa[pos] + 1 - g, t[y].s.insert(pos);
    }
    t[x].s.clear();
  }
  int deg[N];
  long long solve(char *s) {
    for (int i = 1, p = 1; i <= n - 2; i++)
      p = t[p].son[s[i] - 'a'], t[p].s.insert(sa.rk[i + 2]),
      t[p].sum = n - i - 1;
    memset(deg, 0, sizeof(int) * (tot + 1));
    queue<int> q;
    for (int i = 1; i <= tot; i++) ++deg[t[i].fa];
    for (int i = 1; i <= tot; i++)
      if (!deg[i]) q.push(i);
    long long ans = 0;
    while (q.size()) {
      int u = q.front(), f = t[u].fa;
      q.pop();
      ans += t[u].sum * (t[u].len - t[t[u].fa].len);
      merge(u, f);
      if (!--deg[f]) q.push(f);
    }
    return ans;
  }
  long long get() {
    memset(deg, 0, sizeof(int) * (tot + 1));
    for (int i = 1; i <= tot; i++) ++deg[t[i].fa];
    queue<int> q;
    for (int i = 1; i <= tot; i++)
      if (!deg[i]) q.push(i);
    long long ans = 0;
    while (q.size()) {
      int u = q.front(), f = t[u].fa;
      q.pop();
      ans += t[u].len - t[t[u].fa].len;
      t[f].siz += t[u].siz;
      if (!--deg[f]) q.push(f);
    }
    return ans;
  }
  void clear() {
    for (int i = 1; i <= tot; i++) {
      t[i].fa = t[i].len = t[i].siz = 0;
      t[i].sum = 0;
      t[i].s.clear();
      memset(t[i].son, 0, sizeof(t[i].son));
    }
    tot = pre = 1;
  }
} sam;
char s[N];
int main() {
  scanf("%s", s + 1);
  n = strlen(s + 1);
  long long ans = 0;
  sam.build(s + 1, n - 1), ans += sam.get(), sam.clear();
  sam.build(s, n - 1), ans += sam.get(), sam.clear();
  sam.build(s, n);
  ans += sam.get();
  sa.build(s);
  ans += sam.solve(s);
  pr(ans + 2);
  return 0;
}

```