#include <bits/stdc++.h>
using namespace std;
int n, Log[200005], p = 1;
long long ans;
char s[200005];
inline int read() {
  int s = 0, f = 0;
  char ch = getchar();
  while (ch < 48 || ch > 57) f |= (ch == '-'), ch = getchar();
  while (ch > 47 && ch < 58)
    s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
  return f ? -s : s;
}
namespace SA {
int m, Rank[200005], sa[200005], sum[200005], Fir[200005], hgt[200005],
    Sec[200005], mn[200005][20];
void Init() {
  int i, j, p, *x = Rank, *y = Sec;
  m = 200;
  for (i = 1; i <= n; ++i) ++sum[x[i] = s[i]];
  for (i = 1; i <= m; ++i) sum[i] += sum[i - 1];
  for (i = n; i > 0; --i) sa[sum[x[i]]--] = i;
  for (j = 1, p = 1; p < n; j <<= 1, m = p) {
    for (i = n - j + 1, p = 0; i <= n; ++i) y[++p] = i;
    for (i = 1; i <= n; ++i)
      if (sa[i] - j > 0) y[++p] = sa[i] - j;
    for (i = 0; i <= m; ++i) sum[i] = 0;
    for (i = 1; i <= n; ++i) ++sum[Fir[i] = x[y[i]]];
    for (i = 1; i <= m; ++i) sum[i] += sum[i - 1];
    for (i = n; i >= 1; --i) sa[sum[Fir[i]]--] = y[i];
    swap(x, y), x[sa[1]] = 1;
    for (i = 2, p = 1; i <= n; ++i)
      x[sa[i]] = (y[sa[i]] != y[sa[i - 1]] || y[sa[i] + j] != y[sa[i - 1] + j])
                     ? ++p
                     : p;
  }
  for (i = 1; i <= n; ++i) Rank[sa[i]] = i;
  for (i = 1, p = 0; i <= n; ++i) {
    if (Rank[i] == 1)
      hgt[1] = 0;
    else {
      j = sa[Rank[i] - 1];
      while (s[i + p] == s[j + p]) ++p;
      hgt[Rank[i]] = p, p -= p > 0;
    }
  }
  for (i = n; i; --i) {
    mn[i][0] = hgt[i];
    for (j = 1; i + (1 << j) <= n + 1; ++j)
      mn[i][j] = min(mn[i][j - 1], mn[i + (1 << j - 1)][j - 1]);
  }
  for (i = 2; i <= n; ++i) Log[i] = Log[i >> 1] + 1;
}
int Ask(int l, int r) {
  int len = Log[r - l + 1];
  return min(mn[l][len], mn[r - (1 << len) + 1][len]);
}
}  // namespace SA
struct node {
  set<int> st;
  long long vl;
  void insert(int x) {
    if (st.count(x)) return;
    int l = *(--st.lower_bound(x)), r = *st.upper_bound(x);
    vl += n - SA::sa[x] + 1, st.insert(x);
    if (1 <= l) vl -= SA::Ask(l + 1, x);
    if (r <= n) vl -= SA::Ask(x + 1, r);
    if (1 <= l && r <= n) vl += SA::Ask(l + 1, r);
  }
  void init() { st.insert(0), st.insert(n + 1); }
} a[200005];
namespace SAM {
int fa[200005], ch[200005][26], rt, las, tot, len[200005];
vector<int> g[200005];
int New(int x) { return len[++tot] = x, tot; }
void Insert(int w) {
  int p = las, x = New(len[p] + 1);
  for (; p && !ch[p][w]; p = fa[p]) ch[p][w] = x;
  if (!p)
    fa[x] = rt;
  else {
    int q = ch[p][w];
    if (len[q] == len[p] + 1)
      fa[x] = q;
    else {
      int nq = New(len[p] + 1);
      memcpy(ch[nq], ch[q], sizeof(ch[q]));
      fa[nq] = fa[q], fa[q] = fa[x] = nq;
      for (; p && ch[p][w] == q; p = fa[p]) ch[p][w] = nq;
    }
  }
  las = x;
}
void Dfs(int x) {
  for (int y : g[x]) {
    Dfs(y);
    if (a[y].st.size() > a[x].st.size()) swap(a[x], a[y]);
    for (int tmp : a[y].st) a[x].insert(tmp);
  }
  ans += 1ll * (len[x] - len[fa[x]]) * a[x].vl;
}
void Work() {
  for (int i = 2; i <= tot; ++i) g[fa[i]].push_back(i);
  Dfs(1);
}
}  // namespace SAM
int main() {
  scanf("%s", s + 1), n = strlen(s + 1), SAM::rt = SAM::tot = SAM::las = 1;
  for (int i = 1; i <= n; ++i) SAM::Insert(s[i] - 'a');
  SA::Init();
  for (int i = 1; i <= SAM::tot; ++i) a[i].init();
  a[p = 1].insert(SA::Rank[2]);
  for (int i = 1; i <= n; ++i) {
    p = SAM::ch[p][s[i] - 'a'];
    if (i <= n - 2) a[p].insert(SA::Rank[i + 2]);
  }
  SAM::Work(), ans += a[1].vl + 2;
  for (int i = 1; i <= SAM::tot; ++i) {
    ans += SAM::len[i] - SAM::len[SAM::fa[i]];
    if (i != p) ans += SAM::len[i] - SAM::len[SAM::fa[i]];
  }
  cout << ans;
  return 0;
}

### 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>
using namespace std;
int n, Log[200005], p = 1;
long long ans;
char s[200005];
inline int read() {
  int s = 0, f = 0;
  char ch = getchar();
  while (ch < 48 || ch > 57) f |= (ch == '-'), ch = getchar();
  while (ch > 47 && ch < 58)
    s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
  return f ? -s : s;
}
namespace SA {
int m, Rank[200005], sa[200005], sum[200005], Fir[200005], hgt[200005],
    Sec[200005], mn[200005][20];
void Init() {
  int i, j, p, *x = Rank, *y = Sec;
  m = 200;
  for (i = 1; i <= n; ++i) ++sum[x[i] = s[i]];
  for (i = 1; i <= m; ++i) sum[i] += sum[i - 1];
  for (i = n; i > 0; --i) sa[sum[x[i]]--] = i;
  for (j = 1, p = 1; p < n; j <<= 1, m = p) {
    for (i = n - j + 1, p = 0; i <= n; ++i) y[++p] = i;
    for (i = 1; i <= n; ++i)
      if (sa[i] - j > 0) y[++p] = sa[i] - j;
    for (i = 0; i <= m; ++i) sum[i] = 0;
    for (i = 1; i <= n; ++i) ++sum[Fir[i] = x[y[i]]];
    for (i = 1; i <= m; ++i) sum[i] += sum[i - 1];
    for (i = n; i >= 1; --i) sa[sum[Fir[i]]--] = y[i];
    swap(x, y), x[sa[1]] = 1;
    for (i = 2, p = 1; i <= n; ++i)
      x[sa[i]] = (y[sa[i]] != y[sa[i - 1]] || y[sa[i] + j] != y[sa[i - 1] + j])
                     ? ++p
                     : p;
  }
  for (i = 1; i <= n; ++i) Rank[sa[i]] = i;
  for (i = 1, p = 0; i <= n; ++i) {
    if (Rank[i] == 1)
      hgt[1] = 0;
    else {
      j = sa[Rank[i] - 1];
      while (s[i + p] == s[j + p]) ++p;
      hgt[Rank[i]] = p, p -= p > 0;
    }
  }
  for (i = n; i; --i) {
    mn[i][0] = hgt[i];
    for (j = 1; i + (1 << j) <= n + 1; ++j)
      mn[i][j] = min(mn[i][j - 1], mn[i + (1 << j - 1)][j - 1]);
  }
  for (i = 2; i <= n; ++i) Log[i] = Log[i >> 1] + 1;
}
int Ask(int l, int r) {
  int len = Log[r - l + 1];
  return min(mn[l][len], mn[r - (1 << len) + 1][len]);
}
}  // namespace SA
struct node {
  set<int> st;
  long long vl;
  void insert(int x) {
    if (st.count(x)) return;
    int l = *(--st.lower_bound(x)), r = *st.upper_bound(x);
    vl += n - SA::sa[x] + 1, st.insert(x);
    if (1 <= l) vl -= SA::Ask(l + 1, x);
    if (r <= n) vl -= SA::Ask(x + 1, r);
    if (1 <= l && r <= n) vl += SA::Ask(l + 1, r);
  }
  void init() { st.insert(0), st.insert(n + 1); }
} a[200005];
namespace SAM {
int fa[200005], ch[200005][26], rt, las, tot, len[200005];
vector<int> g[200005];
int New(int x) { return len[++tot] = x, tot; }
void Insert(int w) {
  int p = las, x = New(len[p] + 1);
  for (; p && !ch[p][w]; p = fa[p]) ch[p][w] = x;
  if (!p)
    fa[x] = rt;
  else {
    int q = ch[p][w];
    if (len[q] == len[p] + 1)
      fa[x] = q;
    else {
      int nq = New(len[p] + 1);
      memcpy(ch[nq], ch[q], sizeof(ch[q]));
      fa[nq] = fa[q], fa[q] = fa[x] = nq;
      for (; p && ch[p][w] == q; p = fa[p]) ch[p][w] = nq;
    }
  }
  las = x;
}
void Dfs(int x) {
  for (int y : g[x]) {
    Dfs(y);
    if (a[y].st.size() > a[x].st.size()) swap(a[x], a[y]);
    for (int tmp : a[y].st) a[x].insert(tmp);
  }
  ans += 1ll * (len[x] - len[fa[x]]) * a[x].vl;
}
void Work() {
  for (int i = 2; i <= tot; ++i) g[fa[i]].push_back(i);
  Dfs(1);
}
}  // namespace SAM
int main() {
  scanf("%s", s + 1), n = strlen(s + 1), SAM::rt = SAM::tot = SAM::las = 1;
  for (int i = 1; i <= n; ++i) SAM::Insert(s[i] - 'a');
  SA::Init();
  for (int i = 1; i <= SAM::tot; ++i) a[i].init();
  a[p = 1].insert(SA::Rank[2]);
  for (int i = 1; i <= n; ++i) {
    p = SAM::ch[p][s[i] - 'a'];
    if (i <= n - 2) a[p].insert(SA::Rank[i + 2]);
  }
  SAM::Work(), ans += a[1].vl + 2;
  for (int i = 1; i <= SAM::tot; ++i) {
    ans += SAM::len[i] - SAM::len[SAM::fa[i]];
    if (i != p) ans += SAM::len[i] - SAM::len[SAM::fa[i]];
  }
  cout << ans;
  return 0;
}

```