#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;
char str[N];
int n, m, root = 1, lst = 1, cnt = 1;
long long ans = 2, sum[N << 1], sub[N << 1];
int ch[N << 1][26], f[N << 1], len[N << 1];
int x[N], y[N << 1], ed[N], sa[N], rk[N], height[N], bk[N], lg[N], mn[20][N];
set<int> s[N << 1];
inline int lcp(int x, int y) {
  ++x;
  int k = lg[y - x + 1];
  return min(mn[k][x], mn[k][y - (1 << k) + 1]);
}
inline void extend(int c) {
  int p = lst, np = lst = ++cnt;
  len[np] = len[p] + 1;
  for (; p && !ch[p][c]; p = f[p]) ch[p][c] = np;
  if (!p)
    f[np] = root;
  else {
    int q = ch[p][c];
    if (len[q] == len[p] + 1)
      f[np] = q;
    else {
      int nq = ++cnt;
      memcpy(ch[nq], ch[q], sizeof(ch[q]));
      len[nq] = len[p] + 1;
      f[nq] = f[q];
      f[q] = f[np] = nq;
      for (; ch[p][c] == q; p = f[p]) ch[p][c] = nq;
    }
  }
}
int main() {
  scanf("%s", str + 1);
  n = strlen(str + 1);
  m = 200;
  for (int i = 2; i <= n; ++i)
    extend(str[i] - 'a'), ans += len[lst] - len[f[lst]];
  cnt = 1;
  lst = 1;
  root = 1;
  memset(ch, 0, sizeof(ch));
  memset(f, 0, sizeof(f));
  memset(len, 0, sizeof(len));
  for (int i = 1; i < n; ++i)
    extend(str[i] - 'a'), ans += 2 * (len[lst] - len[f[lst]]), ed[i] = lst;
  extend(str[n] - 'a');
  ed[n] = lst;
  ans += len[lst] - len[f[lst]];
  for (int i = 1; i < n - 1; ++i) sum[ed[i]] = n - i - 1;
  for (int i = 1; i <= n; ++i) ++bk[x[i] = str[i]];
  for (int i = 1; i <= m; ++i) bk[i] += bk[i - 1];
  for (int i = 1; i <= n; ++i) sa[bk[x[i]]--] = i;
  for (int len = 1; len <= n; len <<= 1) {
    int num = 0;
    for (int i = n - len + 1; i <= n; ++i) y[++num] = i;
    for (int i = 1; i <= n; ++i)
      if (sa[i] > len) y[++num] = sa[i] - len;
    for (int i = 1; i <= m; ++i) bk[i] = 0;
    for (int i = 1; i <= n; ++i) ++bk[x[i]];
    for (int i = 1; i <= m; ++i) bk[i] += bk[i - 1];
    for (int i = n; i; --i) sa[bk[x[y[i]]]--] = y[i];
    for (int i = 1; i <= n; ++i) y[i] = x[i], x[i] = 0;
    x[sa[1]] = m = 1;
    for (int i = 2; i <= n; ++i)
      x[sa[i]] =
          (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + len] == y[sa[i - 1] + len])
              ? m
              : ++m;
    if (n == m) break;
  }
  for (int i = 1; i <= n; ++i) rk[sa[i]] = i;
  for (int i = 1; i < n - 1; ++i) s[ed[i]].insert(rk[i + 2]);
  for (int i = 1, k = 0; i <= n; ++i) {
    while (str[i + k] == str[sa[rk[i] - 1] + k]) ++k;
    height[rk[i]] = k;
    if (k) --k;
  }
  for (int i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1;
  for (int i = 1; i <= n; ++i) mn[0][i] = height[i];
  for (int i = 1; i <= 18; ++i)
    for (int j = 1; j <= n - (1 << i) + 1; ++j)
      mn[i][j] = min(mn[i - 1][j], mn[i - 1][j + (1 << i - 1)]);
  for (int i = 0; i <= n; ++i) bk[i] = 0;
  for (int i = 1; i <= cnt; ++i) ++bk[len[i]];
  for (int i = 1; i <= n; ++i) bk[i] += bk[i - 1];
  for (int i = 1; i <= cnt; ++i) y[bk[len[i]]--] = i;
  for (int i = cnt; i >= 1; --i) {
    int x = y[i];
    ans += (sum[x] - sub[x]) * (len[x] - len[f[x]]);
    if (s[x].size() > s[f[x]].size())
      swap(s[x], s[f[x]]), swap(sub[x], sub[f[x]]), swap(sum[x], sum[f[x]]);
    sum[f[x]] += sum[x];
    for (auto k : s[x]) {
      auto it = s[f[x]].lower_bound(k);
      if (it != s[f[x]].end() && it != s[f[x]].begin()) {
        auto pre = prev(it);
        sub[f[x]] -= lcp(*pre, *it);
      }
      if (it != s[f[x]].end()) sub[f[x]] += lcp(k, *it);
      if (it != s[f[x]].begin()) --it, sub[f[x]] += lcp(*it, k);
      s[f[x]].insert(k);
    }
  }
  printf("%lld\n", ans);
  return 0;
}

### Prompt

Develop a solution in Cpp 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 = 1e5 + 7;
char str[N];
int n, m, root = 1, lst = 1, cnt = 1;
long long ans = 2, sum[N << 1], sub[N << 1];
int ch[N << 1][26], f[N << 1], len[N << 1];
int x[N], y[N << 1], ed[N], sa[N], rk[N], height[N], bk[N], lg[N], mn[20][N];
set<int> s[N << 1];
inline int lcp(int x, int y) {
  ++x;
  int k = lg[y - x + 1];
  return min(mn[k][x], mn[k][y - (1 << k) + 1]);
}
inline void extend(int c) {
  int p = lst, np = lst = ++cnt;
  len[np] = len[p] + 1;
  for (; p && !ch[p][c]; p = f[p]) ch[p][c] = np;
  if (!p)
    f[np] = root;
  else {
    int q = ch[p][c];
    if (len[q] == len[p] + 1)
      f[np] = q;
    else {
      int nq = ++cnt;
      memcpy(ch[nq], ch[q], sizeof(ch[q]));
      len[nq] = len[p] + 1;
      f[nq] = f[q];
      f[q] = f[np] = nq;
      for (; ch[p][c] == q; p = f[p]) ch[p][c] = nq;
    }
  }
}
int main() {
  scanf("%s", str + 1);
  n = strlen(str + 1);
  m = 200;
  for (int i = 2; i <= n; ++i)
    extend(str[i] - 'a'), ans += len[lst] - len[f[lst]];
  cnt = 1;
  lst = 1;
  root = 1;
  memset(ch, 0, sizeof(ch));
  memset(f, 0, sizeof(f));
  memset(len, 0, sizeof(len));
  for (int i = 1; i < n; ++i)
    extend(str[i] - 'a'), ans += 2 * (len[lst] - len[f[lst]]), ed[i] = lst;
  extend(str[n] - 'a');
  ed[n] = lst;
  ans += len[lst] - len[f[lst]];
  for (int i = 1; i < n - 1; ++i) sum[ed[i]] = n - i - 1;
  for (int i = 1; i <= n; ++i) ++bk[x[i] = str[i]];
  for (int i = 1; i <= m; ++i) bk[i] += bk[i - 1];
  for (int i = 1; i <= n; ++i) sa[bk[x[i]]--] = i;
  for (int len = 1; len <= n; len <<= 1) {
    int num = 0;
    for (int i = n - len + 1; i <= n; ++i) y[++num] = i;
    for (int i = 1; i <= n; ++i)
      if (sa[i] > len) y[++num] = sa[i] - len;
    for (int i = 1; i <= m; ++i) bk[i] = 0;
    for (int i = 1; i <= n; ++i) ++bk[x[i]];
    for (int i = 1; i <= m; ++i) bk[i] += bk[i - 1];
    for (int i = n; i; --i) sa[bk[x[y[i]]]--] = y[i];
    for (int i = 1; i <= n; ++i) y[i] = x[i], x[i] = 0;
    x[sa[1]] = m = 1;
    for (int i = 2; i <= n; ++i)
      x[sa[i]] =
          (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + len] == y[sa[i - 1] + len])
              ? m
              : ++m;
    if (n == m) break;
  }
  for (int i = 1; i <= n; ++i) rk[sa[i]] = i;
  for (int i = 1; i < n - 1; ++i) s[ed[i]].insert(rk[i + 2]);
  for (int i = 1, k = 0; i <= n; ++i) {
    while (str[i + k] == str[sa[rk[i] - 1] + k]) ++k;
    height[rk[i]] = k;
    if (k) --k;
  }
  for (int i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1;
  for (int i = 1; i <= n; ++i) mn[0][i] = height[i];
  for (int i = 1; i <= 18; ++i)
    for (int j = 1; j <= n - (1 << i) + 1; ++j)
      mn[i][j] = min(mn[i - 1][j], mn[i - 1][j + (1 << i - 1)]);
  for (int i = 0; i <= n; ++i) bk[i] = 0;
  for (int i = 1; i <= cnt; ++i) ++bk[len[i]];
  for (int i = 1; i <= n; ++i) bk[i] += bk[i - 1];
  for (int i = 1; i <= cnt; ++i) y[bk[len[i]]--] = i;
  for (int i = cnt; i >= 1; --i) {
    int x = y[i];
    ans += (sum[x] - sub[x]) * (len[x] - len[f[x]]);
    if (s[x].size() > s[f[x]].size())
      swap(s[x], s[f[x]]), swap(sub[x], sub[f[x]]), swap(sum[x], sum[f[x]]);
    sum[f[x]] += sum[x];
    for (auto k : s[x]) {
      auto it = s[f[x]].lower_bound(k);
      if (it != s[f[x]].end() && it != s[f[x]].begin()) {
        auto pre = prev(it);
        sub[f[x]] -= lcp(*pre, *it);
      }
      if (it != s[f[x]].end()) sub[f[x]] += lcp(k, *it);
      if (it != s[f[x]].begin()) --it, sub[f[x]] += lcp(*it, k);
      s[f[x]].insert(k);
    }
  }
  printf("%lld\n", ans);
  return 0;
}

```