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.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
struct MI {
 private:
  char bb[4096];
  FILE* f;
  char *bs, *be;
  char e;
  bool o, l;

 public:
  MI() : f(stdin) {}
  inline char get() {
    if (o) {
      o = 0;
      return e;
    }
    if (bs == be) be = (bs = bb) + fread(bb, 1, sizeof(bb), f);
    if (bs == be) {
      l = 1;
      return -1;
    };
    return *bs++;
  }
  template <typename T>
  inline T read() {
    T r;
    *this > r;
    return r;
  }
  template <typename T>
  inline MI& operator>(T&);
};
template <typename T>
struct Q {
  const static bool U = T(-1) >= T(0);
};
template <>
struct Q<char> {
  inline void operator()(MI& t, char& r) {
    int c;
    for (;;) {
      c = t.get();
      if (c == -1) {
        r = -1;
        return;
      };
      if (!isspace(c)) {
        r = c;
        return;
      };
    }
  }
};
template <typename T>
inline MI& MI::operator>(T& t) {
  Q<T>()(*this, t);
  return *this;
}
template <typename T>
std::ostream& operator<(std::ostream& out, const T& t) {
  return out << t;
}
using std::cout;
using std::set;
MI cin;
const int nmax = 200001;
const int S = nmax * 2;
const int cmax = 26;
char s[nmax];
int ind[nmax];
namespace graph {
int lst[S], pre[S], tar[S];
int son[S], siz[S], top[S], dep[S], fa[S];
inline void link(int x, int y) {
  static int tot;
  pre[++tot] = lst[x];
  lst[x] = tot;
  tar[tot] = y;
}
void dfs(int x) {
  static int tot;
  dep[x] = dep[fa[x]] + 1;
  siz[x] = 1;
  ind[x] = ++tot;
  for (int b = lst[x], v = tar[b]; b; v = tar[b = pre[b]]) {
    if (v == fa[x]) continue;
    fa[v] = x;
    dfs(v);
    siz[x] += siz[v];
    if (siz[v] > siz[son[x]]) son[x] = v;
  }
}
void load(int x, int t) {
  top[x] = t;
  if (son[x]) load(son[x], t);
  for (int b = lst[x], v = tar[b]; b; v = tar[b = pre[b]]) {
    if (v == fa[x] || v == son[x]) continue;
    load(v, v);
  }
}
inline void init() {
  dfs(1);
  load(1, 1);
}
inline int lca(int x, int y) {
  while (top[x] != top[y]) {
    if (dep[top[x]] < dep[top[y]]) std::swap(x, y);
    x = fa[top[x]];
  }
  return dep[x] < dep[y] ? x : y;
}
}  // namespace graph
struct node_cmp_t {
  inline bool operator()(int x, int y) const { return ind[x] < ind[y]; }
};
set<int, node_cmp_t> w[S];
int too[nmax], seq[S];
long long siz[S];
inline void merge(int x, int y);
struct sam {
  int tar[S][cmax], pre[S], len[S], nod[nmax];
  int lst = 1, tot = 1;
  inline int node(int l) {
    len[++tot] = l;
    return tot;
  }
  inline void insert(int p) {
    const int c = s[p];
    int i = lst;
    lst = nod[p] = node(len[i] + 1);
    while (!tar[i][c]) {
      tar[i][c] = lst;
      if (!(i = pre[i])) return (void)(pre[lst] = 1);
    }
    const int ori = tar[i][c];
    if (len[i] + 1 == len[ori]) return (void)(pre[lst] = ori);
    const int sub = node(len[i] + 1);
    memcpy(tar[sub], tar[ori], sizeof(tar[0]));
    pre[sub] = pre[ori];
    pre[lst] = pre[ori] = sub;
    do {
      tar[i][c] = sub;
      i = pre[i];
    } while (i && tar[i][c] == ori);
  }
  inline long long count() {
    long long ret = 1;
    for (int i = 2; i <= tot; ++i) ret += len[i] - len[pre[i]];
    return ret;
  }
  inline void init() {
    for (int i = 2; i <= tot; ++i) graph::link(pre[i], i);
    graph::init();
    for (int i = 1; i <= tot; ++i) ++len[i];
  }
  inline long long solve() {
    const int n = len[lst];
    for (int i = 1; i <= tot; ++i) ++too[len[i]];
    for (int i = 1; i <= n; ++i) too[i] += too[i - 1];
    for (int i = 1; i <= tot; ++i) seq[too[len[i]]--] = i;
    for (int i = 1; i <= tot; ++i) ++len[i];
    long long ret = 0;
    for (int i = tot; i; --i) {
      const int x = seq[i];
      ret += (long long)(len[x] - len[pre[x]]) * siz[x];
      if (pre[x]) merge(pre[x], x);
    }
    return ret;
  }
} fo, re;
inline void merge(int x, int y) {
  auto &a = w[x], &b = w[y];
  if (a.size() < b.size()) {
    std::swap(a, b);
    std::swap(siz[x], siz[y]);
  }
  for (int i : b) {
    siz[x] += re.len[i];
    if (a.empty()) {
      a.insert(i);
      assert(siz[x] == re.len[i]);
    } else {
      auto iter = a.lower_bound(i);
      if (iter != a.end() && *iter == i) continue;
      if (iter == a.begin()) {
        siz[x] -= re.len[graph::lca(*iter, i)];
      } else if (iter == a.end()) {
        siz[x] -= re.len[graph::lca(*--iter, i)];
      } else {
        auto pre = iter;
        --pre;
        siz[x] += re.len[graph::lca(*pre, *iter)];
        siz[x] -= re.len[graph::lca(*pre, i)];
        siz[x] -= re.len[graph::lca(i, *iter)];
      }
      a.insert(iter, i);
    }
  }
}
int n;
int main() {
  char c = cin.read<char>();
  while (c != -1 && !isspace(c)) {
    s[++n] = c - 'a';
    c = cin.get();
  }
  for (int i = 1; i <= n; ++i) {
    fo.insert(i);
    re.insert(n - i + 1);
  }
  fo.nod[0] = 1;
  re.nod[n + 1] = 1;
  re.init();
  long long ans = fo.count();
  for (int i = 2; i <= n + 1; ++i) {
    w[fo.nod[i - 2]].insert(re.nod[i]);
    siz[fo.nod[i - 2]] = re.len[re.nod[i]];
  }
  ans += fo.solve();
  cout < ans < ('\n');
  return 0;
}