#include <bits/stdc++.h>
using namespace std;
const long long maxn = 4e5 + 10;
long long n, dfn[maxn], id[maxn], tot, ret;
long long dis[maxn], anc[maxn][20], ans, g[maxn], val[maxn];
set<long long> Set[maxn];
char s[maxn];
struct SAM {
  struct node {
    long long len, fa, Next[26];
  } Tree[maxn];
  long long lst = 1, tot = 1, Begin[maxn], Next[maxn], To[maxn], e;
  bool op;
  inline void add(long long u, long long v) {
    To[++e] = v;
    Next[e] = Begin[u];
    Begin[u] = e;
  }
  inline void Update(long long pos, long long num) {
    if (op == 0 && num == n) return;
    if (op == 1 && num == 1) return;
    ans += Tree[pos].len - Tree[Tree[pos].fa].len;
  }
  inline void Extand(long long c, long long x) {
    long long cur = ++tot, p = lst;
    lst = cur;
    Tree[cur].len = Tree[p].len + 1;
    if (op == 0)
      Set[tot].insert(x);
    else
      g[x] = tot;
    while (p && !Tree[p].Next[c]) {
      Tree[p].Next[c] = cur;
      p = Tree[p].fa;
    }
    if (!p) {
      Tree[cur].fa = 1;
      Update(cur, x);
      return;
    }
    long long q = Tree[p].Next[c];
    if (Tree[p].len + 1 == Tree[q].len) {
      Tree[cur].fa = q;
      Update(cur, x);
      return;
    }
    long long clone = ++tot;
    Tree[clone] = Tree[q];
    Tree[clone].len = Tree[p].len + 1;
    while (p && Tree[p].Next[c] == q) {
      Tree[p].Next[c] = clone;
      p = Tree[p].fa;
    }
    Tree[q].fa = Tree[cur].fa = clone;
    Update(cur, x);
  }
  inline void Build() {
    for (long long i = (2), _end_ = (tot); i <= _end_; ++i) add(Tree[i].fa, i);
  }
} A, B;
inline long long LCA(long long x, long long y) {
  if (dis[x] < dis[y]) swap(x, y);
  for (long long i = 18; i >= 0; --i)
    if (dis[anc[x][i]] >= dis[y]) x = anc[x][i];
  if (x == y) return x;
  for (long long i = 18; i >= 0; --i)
    if (anc[x][i] != anc[y][i]) {
      x = anc[x][i];
      y = anc[y][i];
    }
  return anc[x][0];
}
inline void DFS1(long long u) {
  dfn[u] = ++tot;
  id[tot] = u;
  for (long long j = (1), _end_ = (18); j <= _end_; ++j)
    anc[u][j] = anc[anc[u][j - 1]][j - 1];
  for (long long i = B.Begin[u]; i; i = B.Next[i]) {
    long long v = B.To[i];
    anc[v][0] = u;
    dis[v] = dis[u] + 1;
    DFS1(v);
  }
}
inline long long Get(long long x) { return B.Tree[x].len; }
inline void DFS2(long long u) {
  Set[0] = Set[u];
  Set[u].clear();
  for (auto it : Set[0])
    if (it + 2 <= n) {
      long long x = dfn[g[it + 2]];
      Set[u].insert(x);
      val[u] += Get(g[it + 2]);
    }
  for (long long i = A.Begin[u]; i; i = A.Next[i]) {
    long long v = A.To[i];
    DFS2(v);
    if (Set[v].size() > Set[u].size()) {
      swap(Set[u], Set[v]);
      swap(val[u], val[v]);
    }
    for (auto it : Set[v]) {
      auto j = Set[u].lower_bound(it);
      if (j == Set[u].end()) {
        val[u] += Get(id[it]);
        if (j != Set[u].begin()) {
          --j;
          val[u] -= Get(LCA(id[*j], id[it]));
        }
        Set[u].insert(it);
      } else if (*j != it) {
        auto itr = j, itl = j;
        val[u] += Get(id[it]) - Get(LCA(id[*itr], id[it]));
        if (itr != Set[u].begin()) {
          --itl;
          val[u] += Get(LCA(id[*itl], id[*itr]));
          val[u] -= Get(LCA(id[*itl], id[it]));
        }
        Set[u].insert(it);
      }
    }
  }
  long long x = A.Tree[u].len - A.Tree[A.Tree[u].fa].len;
  ans += x;
  ret += val[u] * x;
}
signed main() {
  scanf("%s", s + 1);
  n = strlen(s + 1);
  B.op = true;
  for (long long i = (1), _end_ = (n); i <= _end_; ++i) A.Extand(s[i] - 'a', i);
  for (long long i = n; i >= 1; --i) B.Extand(s[i] - 'a', i);
  A.Build();
  B.Build();
  dis[1] = 1;
  DFS1(1);
  DFS2(1);
  ans = ans + 2 + ret;
  printf("%lld\n", ans);
  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 long long maxn = 4e5 + 10;
long long n, dfn[maxn], id[maxn], tot, ret;
long long dis[maxn], anc[maxn][20], ans, g[maxn], val[maxn];
set<long long> Set[maxn];
char s[maxn];
struct SAM {
  struct node {
    long long len, fa, Next[26];
  } Tree[maxn];
  long long lst = 1, tot = 1, Begin[maxn], Next[maxn], To[maxn], e;
  bool op;
  inline void add(long long u, long long v) {
    To[++e] = v;
    Next[e] = Begin[u];
    Begin[u] = e;
  }
  inline void Update(long long pos, long long num) {
    if (op == 0 && num == n) return;
    if (op == 1 && num == 1) return;
    ans += Tree[pos].len - Tree[Tree[pos].fa].len;
  }
  inline void Extand(long long c, long long x) {
    long long cur = ++tot, p = lst;
    lst = cur;
    Tree[cur].len = Tree[p].len + 1;
    if (op == 0)
      Set[tot].insert(x);
    else
      g[x] = tot;
    while (p && !Tree[p].Next[c]) {
      Tree[p].Next[c] = cur;
      p = Tree[p].fa;
    }
    if (!p) {
      Tree[cur].fa = 1;
      Update(cur, x);
      return;
    }
    long long q = Tree[p].Next[c];
    if (Tree[p].len + 1 == Tree[q].len) {
      Tree[cur].fa = q;
      Update(cur, x);
      return;
    }
    long long clone = ++tot;
    Tree[clone] = Tree[q];
    Tree[clone].len = Tree[p].len + 1;
    while (p && Tree[p].Next[c] == q) {
      Tree[p].Next[c] = clone;
      p = Tree[p].fa;
    }
    Tree[q].fa = Tree[cur].fa = clone;
    Update(cur, x);
  }
  inline void Build() {
    for (long long i = (2), _end_ = (tot); i <= _end_; ++i) add(Tree[i].fa, i);
  }
} A, B;
inline long long LCA(long long x, long long y) {
  if (dis[x] < dis[y]) swap(x, y);
  for (long long i = 18; i >= 0; --i)
    if (dis[anc[x][i]] >= dis[y]) x = anc[x][i];
  if (x == y) return x;
  for (long long i = 18; i >= 0; --i)
    if (anc[x][i] != anc[y][i]) {
      x = anc[x][i];
      y = anc[y][i];
    }
  return anc[x][0];
}
inline void DFS1(long long u) {
  dfn[u] = ++tot;
  id[tot] = u;
  for (long long j = (1), _end_ = (18); j <= _end_; ++j)
    anc[u][j] = anc[anc[u][j - 1]][j - 1];
  for (long long i = B.Begin[u]; i; i = B.Next[i]) {
    long long v = B.To[i];
    anc[v][0] = u;
    dis[v] = dis[u] + 1;
    DFS1(v);
  }
}
inline long long Get(long long x) { return B.Tree[x].len; }
inline void DFS2(long long u) {
  Set[0] = Set[u];
  Set[u].clear();
  for (auto it : Set[0])
    if (it + 2 <= n) {
      long long x = dfn[g[it + 2]];
      Set[u].insert(x);
      val[u] += Get(g[it + 2]);
    }
  for (long long i = A.Begin[u]; i; i = A.Next[i]) {
    long long v = A.To[i];
    DFS2(v);
    if (Set[v].size() > Set[u].size()) {
      swap(Set[u], Set[v]);
      swap(val[u], val[v]);
    }
    for (auto it : Set[v]) {
      auto j = Set[u].lower_bound(it);
      if (j == Set[u].end()) {
        val[u] += Get(id[it]);
        if (j != Set[u].begin()) {
          --j;
          val[u] -= Get(LCA(id[*j], id[it]));
        }
        Set[u].insert(it);
      } else if (*j != it) {
        auto itr = j, itl = j;
        val[u] += Get(id[it]) - Get(LCA(id[*itr], id[it]));
        if (itr != Set[u].begin()) {
          --itl;
          val[u] += Get(LCA(id[*itl], id[*itr]));
          val[u] -= Get(LCA(id[*itl], id[it]));
        }
        Set[u].insert(it);
      }
    }
  }
  long long x = A.Tree[u].len - A.Tree[A.Tree[u].fa].len;
  ans += x;
  ret += val[u] * x;
}
signed main() {
  scanf("%s", s + 1);
  n = strlen(s + 1);
  B.op = true;
  for (long long i = (1), _end_ = (n); i <= _end_; ++i) A.Extand(s[i] - 'a', i);
  for (long long i = n; i >= 1; --i) B.Extand(s[i] - 'a', i);
  A.Build();
  B.Build();
  dis[1] = 1;
  DFS1(1);
  DFS2(1);
  ans = ans + 2 + ret;
  printf("%lld\n", ans);
  return 0;
}

```