#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e5;
string s;
int n;
struct node {
  int l, r, par, link;
  map<char, int> next;
  node(int l = 0, int r = 0, int par = -1) : l(l), r(r), par(par), link(-1) {}
  int len() { return r - l; }
  int& get(char c) {
    if (!next.count(c)) next[c] = -1;
    return next[c];
  }
};
node t[MAXN];
int sz;
struct state {
  int v, pos;
  state(int v, int pos) : v(v), pos(pos) {}
};
state ptr(0, 0);
state go(state st, int l, int r) {
  while (l < r)
    if (st.pos == t[st.v].len()) {
      st = state(t[st.v].get(s[l]), 0);
      if (st.v == -1) return st;
    } else {
      if (s[t[st.v].l + st.pos] != s[l]) return state(-1, -1);
      if (r - l < t[st.v].len() - st.pos) return state(st.v, st.pos + r - l);
      l += t[st.v].len() - st.pos;
      st.pos = t[st.v].len();
    }
  return st;
}
int split(state st) {
  if (st.pos == t[st.v].len()) return st.v;
  if (st.pos == 0) return t[st.v].par;
  node v = t[st.v];
  int id = sz++;
  t[id] = node(v.l, v.l + st.pos, v.par);
  t[v.par].get(s[v.l]) = id;
  t[id].get(s[v.l + st.pos]) = st.v;
  t[st.v].par = id;
  t[st.v].l += st.pos;
  return id;
}
int get_link(int v) {
  if (t[v].link != -1) return t[v].link;
  if (t[v].par == -1) return 0;
  int to = get_link(t[v].par);
  return t[v].link = split(
             go(state(to, t[to].len()), t[v].l + (t[v].par == 0), t[v].r));
}
void tree_extend(int pos) {
  for (;;) {
    state nptr = go(ptr, pos, pos + 1);
    if (nptr.v != -1) {
      ptr = nptr;
      return;
    }
    int mid = split(ptr);
    int leaf = sz++;
    t[leaf] = node(pos, n, mid);
    t[mid].get(s[pos]) = leaf;
    ptr.v = get_link(mid);
    ptr.pos = t[ptr.v].len();
    if (!mid) break;
  }
}
void build_tree() {
  sz = 1;
  for (int i = 0; i < n; ++i) tree_extend(i);
}
template <typename T, class F = function<T(const T&, const T&)>>
class SparseTable {
 public:
  int n;
  vector<vector<T>> mat;
  F func;
  SparseTable(const vector<T>& a, const F& f) : func(f) {
    n = static_cast<int>(a.size());
    int max_log = 32 - __builtin_clz(n);
    mat.resize(max_log);
    mat[0] = a;
    for (int j = 1; j < max_log; j++) {
      mat[j].resize(n - (1 << j) + 1);
      for (int i = 0; i <= n - (1 << j); i++) {
        mat[j][i] = func(mat[j - 1][i], mat[j - 1][i + (1 << (j - 1))]);
      }
    }
  }
  T get(int from, int to) const {
    assert(0 <= from && from <= to && to <= n - 1);
    int lg = 32 - __builtin_clz(to - from + 1) - 1;
    return func(mat[lg][from], mat[lg][to - (1 << lg) + 1]);
  }
};
template <typename T>
void debug_out(T t) {
  cerr << t;
}
template <typename A, typename B>
void debug_out(pair<A, B> u) {
  cerr << "(" << u.first << " " << u.second << ")";
}
template <typename T>
void debug_out(vector<T> t) {
  int sz = t.size();
  for (int i = 0; i < sz; i++) {
    debug_out(t[i]);
    if (i != sz - 1) cerr << ", ";
  }
}
template <typename T>
void debug_out(vector<vector<T>> t) {
  int sz = t.size();
  for (int i = 0; i < sz; i++) {
    debug_out(t[i]);
    if (i != sz - 1) cerr << endl;
  }
}
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  debug_out(H);
  cerr << " ";
  debug_out(T...);
}
int main() {
  cin >> s;
  reverse(s.begin(), s.end());
  n = s.length();
  long long res = 1;
  build_tree();
  ptr = state(0, 0);
  ptr = go(ptr, 0, n);
  int c = split(ptr);
  vector<pair<int, int>> sig = {{c, 0}};
  for (int i = 1; i < n + 1; i++) {
    c = get_link(c);
    sig.emplace_back(c, i);
  }
  for (int i = 0; i < sz; i++) res += t[i].len();
  vector<int> masked(n + 1);
  for (auto i : sig) masked[n - i.second] = i.first;
  vector<int> dep(sz);
  vector<int> in(sz), out(sz);
  vector<int> tour;
  dep[0] = 1;
  function<void(int, int)> dfs = [&](int v, int p) {
    if (~p) dep[v] = dep[p] + t[v].len();
    in[v] = tour.size();
    tour.push_back(v);
    for (auto it : t[v].next) {
      int u = it.second;
      dfs(u, v);
      tour.push_back(v);
    }
    out[v] = tour.size() - 1;
  };
  dfs(0, -1);
  SparseTable<int> st(tour, [&](int i, int j) {
    return (dep[i] == dep[j] ? min(i, j) : (dep[i] < dep[j] ? i : j));
  });
  auto par = [&](int u, int v) {
    return st.get(min(in[u], in[v]), max(out[u], out[v]));
  };
  reverse(s.begin(), s.end());
  for (int i = 0; i < sz; i++) t[i] = node();
  sz = 0;
  ptr = state(0, 0);
  build_tree();
  ptr = state(0, 0);
  ptr = go(ptr, 0, n);
  c = split(ptr);
  sig = {{c, 0}};
  for (int i = 1; i < n + 1; i++) {
    c = get_link(c);
    sig.emplace_back(c, i);
  }
  vector<vector<int>> to(sz);
  for (auto i : sig) to[i.first].push_back(i.second);
  vector<int> sub(sz, 1);
  vector<long long> ans(sz);
  function<void(int, int)> dfs2 = [&](int v, int p) {
    for (auto it : t[v].next) {
      int u = it.second;
      dfs2(u, v);
      sub[v] += sub[u];
    }
  };
  dfs2(0, -1);
  function<void(int, int)> dfs3 = [&](int v, int p) {
    set<pair<int, int>> cur;
    long long s = 0;
    vector<int> pat = {v};
    while (true) {
      int nxt = -1;
      for (auto it : t[v].next) {
        int i = it.second;
        if (nxt == -1 || sub[i] > sub[nxt]) nxt = i;
      }
      if (nxt == -1) break;
      for (auto it : t[v].next) {
        int i = it.second;
        if (i == nxt) continue;
        dfs3(i, v);
      }
      pat.push_back(nxt);
      v = nxt;
    }
    auto add = [&](int u) {
      if (u < 0) return;
      u = masked[u];
      if (cur.empty()) {
        s += dep[u];
        cur.insert({in[u], u});
        return;
      }
      auto ss = cur.insert({in[u], u});
      auto it = ss.first;
      if (!ss.second) return;
      int z = -1;
      if (it != cur.begin()) {
        z = par(prev(it)->second, u);
      }
      if (next(it) != cur.end() &&
          (z == -1 || dep[z] < dep[par(u, next(it)->second)])) {
        z = par(u, next(it)->second);
      }
      assert(~z);
      s += dep[u] - dep[z];
    };
    reverse(pat.begin(), pat.end());
    int tt = pat.back();
    for (int u : pat) {
      for (int z : to[u]) {
        if (u != tt) to[tt].push_back(z);
        add(z - 1);
      }
      int nxt = -1;
      for (auto it : t[u].next) {
        int i = it.second;
        if (nxt == -1 || sub[i] > sub[nxt]) nxt = i;
      }
      for (auto it : t[u].next) {
        int i = it.second;
        if (i == nxt) continue;
        for (int z : to[i]) {
          to[tt].push_back(z);
          add(z - 1);
        }
      }
      ans[u] = s;
    }
  };
  dfs3(0, -1);
  res += ans[0];
  for (int i = 1; i < sz; i++) {
    res += 1LL * ans[i] * t[i].len();
  }
  cout << res;
  return 0;
}

### Prompt

Please create a solution in cpp 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 MAXN = 5e5;
string s;
int n;
struct node {
  int l, r, par, link;
  map<char, int> next;
  node(int l = 0, int r = 0, int par = -1) : l(l), r(r), par(par), link(-1) {}
  int len() { return r - l; }
  int& get(char c) {
    if (!next.count(c)) next[c] = -1;
    return next[c];
  }
};
node t[MAXN];
int sz;
struct state {
  int v, pos;
  state(int v, int pos) : v(v), pos(pos) {}
};
state ptr(0, 0);
state go(state st, int l, int r) {
  while (l < r)
    if (st.pos == t[st.v].len()) {
      st = state(t[st.v].get(s[l]), 0);
      if (st.v == -1) return st;
    } else {
      if (s[t[st.v].l + st.pos] != s[l]) return state(-1, -1);
      if (r - l < t[st.v].len() - st.pos) return state(st.v, st.pos + r - l);
      l += t[st.v].len() - st.pos;
      st.pos = t[st.v].len();
    }
  return st;
}
int split(state st) {
  if (st.pos == t[st.v].len()) return st.v;
  if (st.pos == 0) return t[st.v].par;
  node v = t[st.v];
  int id = sz++;
  t[id] = node(v.l, v.l + st.pos, v.par);
  t[v.par].get(s[v.l]) = id;
  t[id].get(s[v.l + st.pos]) = st.v;
  t[st.v].par = id;
  t[st.v].l += st.pos;
  return id;
}
int get_link(int v) {
  if (t[v].link != -1) return t[v].link;
  if (t[v].par == -1) return 0;
  int to = get_link(t[v].par);
  return t[v].link = split(
             go(state(to, t[to].len()), t[v].l + (t[v].par == 0), t[v].r));
}
void tree_extend(int pos) {
  for (;;) {
    state nptr = go(ptr, pos, pos + 1);
    if (nptr.v != -1) {
      ptr = nptr;
      return;
    }
    int mid = split(ptr);
    int leaf = sz++;
    t[leaf] = node(pos, n, mid);
    t[mid].get(s[pos]) = leaf;
    ptr.v = get_link(mid);
    ptr.pos = t[ptr.v].len();
    if (!mid) break;
  }
}
void build_tree() {
  sz = 1;
  for (int i = 0; i < n; ++i) tree_extend(i);
}
template <typename T, class F = function<T(const T&, const T&)>>
class SparseTable {
 public:
  int n;
  vector<vector<T>> mat;
  F func;
  SparseTable(const vector<T>& a, const F& f) : func(f) {
    n = static_cast<int>(a.size());
    int max_log = 32 - __builtin_clz(n);
    mat.resize(max_log);
    mat[0] = a;
    for (int j = 1; j < max_log; j++) {
      mat[j].resize(n - (1 << j) + 1);
      for (int i = 0; i <= n - (1 << j); i++) {
        mat[j][i] = func(mat[j - 1][i], mat[j - 1][i + (1 << (j - 1))]);
      }
    }
  }
  T get(int from, int to) const {
    assert(0 <= from && from <= to && to <= n - 1);
    int lg = 32 - __builtin_clz(to - from + 1) - 1;
    return func(mat[lg][from], mat[lg][to - (1 << lg) + 1]);
  }
};
template <typename T>
void debug_out(T t) {
  cerr << t;
}
template <typename A, typename B>
void debug_out(pair<A, B> u) {
  cerr << "(" << u.first << " " << u.second << ")";
}
template <typename T>
void debug_out(vector<T> t) {
  int sz = t.size();
  for (int i = 0; i < sz; i++) {
    debug_out(t[i]);
    if (i != sz - 1) cerr << ", ";
  }
}
template <typename T>
void debug_out(vector<vector<T>> t) {
  int sz = t.size();
  for (int i = 0; i < sz; i++) {
    debug_out(t[i]);
    if (i != sz - 1) cerr << endl;
  }
}
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  debug_out(H);
  cerr << " ";
  debug_out(T...);
}
int main() {
  cin >> s;
  reverse(s.begin(), s.end());
  n = s.length();
  long long res = 1;
  build_tree();
  ptr = state(0, 0);
  ptr = go(ptr, 0, n);
  int c = split(ptr);
  vector<pair<int, int>> sig = {{c, 0}};
  for (int i = 1; i < n + 1; i++) {
    c = get_link(c);
    sig.emplace_back(c, i);
  }
  for (int i = 0; i < sz; i++) res += t[i].len();
  vector<int> masked(n + 1);
  for (auto i : sig) masked[n - i.second] = i.first;
  vector<int> dep(sz);
  vector<int> in(sz), out(sz);
  vector<int> tour;
  dep[0] = 1;
  function<void(int, int)> dfs = [&](int v, int p) {
    if (~p) dep[v] = dep[p] + t[v].len();
    in[v] = tour.size();
    tour.push_back(v);
    for (auto it : t[v].next) {
      int u = it.second;
      dfs(u, v);
      tour.push_back(v);
    }
    out[v] = tour.size() - 1;
  };
  dfs(0, -1);
  SparseTable<int> st(tour, [&](int i, int j) {
    return (dep[i] == dep[j] ? min(i, j) : (dep[i] < dep[j] ? i : j));
  });
  auto par = [&](int u, int v) {
    return st.get(min(in[u], in[v]), max(out[u], out[v]));
  };
  reverse(s.begin(), s.end());
  for (int i = 0; i < sz; i++) t[i] = node();
  sz = 0;
  ptr = state(0, 0);
  build_tree();
  ptr = state(0, 0);
  ptr = go(ptr, 0, n);
  c = split(ptr);
  sig = {{c, 0}};
  for (int i = 1; i < n + 1; i++) {
    c = get_link(c);
    sig.emplace_back(c, i);
  }
  vector<vector<int>> to(sz);
  for (auto i : sig) to[i.first].push_back(i.second);
  vector<int> sub(sz, 1);
  vector<long long> ans(sz);
  function<void(int, int)> dfs2 = [&](int v, int p) {
    for (auto it : t[v].next) {
      int u = it.second;
      dfs2(u, v);
      sub[v] += sub[u];
    }
  };
  dfs2(0, -1);
  function<void(int, int)> dfs3 = [&](int v, int p) {
    set<pair<int, int>> cur;
    long long s = 0;
    vector<int> pat = {v};
    while (true) {
      int nxt = -1;
      for (auto it : t[v].next) {
        int i = it.second;
        if (nxt == -1 || sub[i] > sub[nxt]) nxt = i;
      }
      if (nxt == -1) break;
      for (auto it : t[v].next) {
        int i = it.second;
        if (i == nxt) continue;
        dfs3(i, v);
      }
      pat.push_back(nxt);
      v = nxt;
    }
    auto add = [&](int u) {
      if (u < 0) return;
      u = masked[u];
      if (cur.empty()) {
        s += dep[u];
        cur.insert({in[u], u});
        return;
      }
      auto ss = cur.insert({in[u], u});
      auto it = ss.first;
      if (!ss.second) return;
      int z = -1;
      if (it != cur.begin()) {
        z = par(prev(it)->second, u);
      }
      if (next(it) != cur.end() &&
          (z == -1 || dep[z] < dep[par(u, next(it)->second)])) {
        z = par(u, next(it)->second);
      }
      assert(~z);
      s += dep[u] - dep[z];
    };
    reverse(pat.begin(), pat.end());
    int tt = pat.back();
    for (int u : pat) {
      for (int z : to[u]) {
        if (u != tt) to[tt].push_back(z);
        add(z - 1);
      }
      int nxt = -1;
      for (auto it : t[u].next) {
        int i = it.second;
        if (nxt == -1 || sub[i] > sub[nxt]) nxt = i;
      }
      for (auto it : t[u].next) {
        int i = it.second;
        if (i == nxt) continue;
        for (int z : to[i]) {
          to[tt].push_back(z);
          add(z - 1);
        }
      }
      ans[u] = s;
    }
  };
  dfs3(0, -1);
  res += ans[0];
  for (int i = 1; i < sz; i++) {
    res += 1LL * ans[i] * t[i].len();
  }
  cout << res;
  return 0;
}

```