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) {}
  MI(FILE* f) : f(f), bs(0), be(0) {}
  MI(const char* s) : f(fmemopen(const_cast<char*>(s), strlen(s), "r")) {}
  inline operator bool() { return !l; }
  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++;
  }
  inline void unget(char c) {
    o = 1;
    e = c;
  }
  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);
  inline void operator()(MI& t, T& r) const {
    r = 0;
    char c;
    bool y = 0;
    if (U)
      for (;;) {
        c = t.get();
        if (c == -1) goto E;
        if (isdigit(c)) break;
      }
    else
      for (;;) {
        c = t.get();
        if (c == -1) goto E;
        if (c == '-') {
          c = t.get();
          if (isdigit(c)) {
            y = 1;
            break;
          };
        } else if (isdigit(c))
          break;
        ;
      };
    for (;;) {
      if (c == -1) goto E;
      if (isdigit(c))
        r = r * 10 + (c ^ 48);
      else
        break;
      c = t.get();
    }
    t.unget(c);
  E:;
    if (y) r = -r;
  }
};
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;
MI cin;
const int nmax = 100001;
const int cmax = 26;
const int S = nmax * 2;
template <typename T>
inline bool getmin(T& a, const T& b) {
  return a > b && (a = b, true);
}
template <typename T>
inline bool getmax(T& a, const T& b) {
  return a < b && (a = b, true);
}
int* dis;
template <int pmax>
struct graph {
  int lst[pmax];
  int pre[pmax], tar[pmax];
  int tot;
  int fa[pmax], siz[pmax], son[pmax], top[pmax];
  int ind[pmax], rin[pmax];
  inline void link(int x, int y) {
    pre[++tot] = lst[x];
    lst[x] = tot;
    tar[tot] = y;
  }
  void load1(int x) {
    static int tot = 0;
    siz[x] = 1;
    ind[x] = ++tot;
    rin[tot] = x;
    for (int b = lst[x], v = tar[b]; b; v = tar[b = pre[b]]) {
      fa[v] = x;
      assert(dis[v] > dis[x]);
      load1(v);
      siz[x] += siz[v];
      if (siz[v] > siz[son[x]]) son[x] = v;
    }
  }
  void load2(int x, int t) {
    top[x] = t;
    if (son[x]) load2(son[x], t);
    for (int b = lst[x], v = tar[b]; b; v = tar[b = pre[b]]) {
      if (v == son[x]) continue;
      load2(v, v);
    }
  }
  inline void load() {
    load1(1);
    load2(1, 1);
  }
  inline int lca(int x, int y) {
    while (top[x] != top[y]) {
      if (dis[top[x]] < dis[top[y]]) std::swap(x, y);
      x = fa[top[x]];
    }
    return dis[x] < dis[y] ? x : y;
  }
};
graph<S> g;
int N;
namespace itr {
const int tmax = 6000000;
int lef[tmax], rig[tmax], lm[tmax], rm[tmax];
long long sum[tmax];
int ii;
int tot;
inline void pu(int x) {
  assert(lef[x] || rig[x]);
  if (lef[x] && rig[x])
    sum[x] = sum[lef[x]] + sum[rig[x]] -
             dis[g.lca(g.rin[rm[lef[x]]], g.rin[lm[rig[x]]])];
  else
    sum[x] = sum[lef[x] ? lef[x] : rig[x]];
  lm[x] = lm[lef[x] ? lef[x] : rig[x]];
  rm[x] = rm[rig[x] ? rig[x] : lef[x]];
}
inline void _update(int& x, int l, int r) {
  if (!x) x = ++tot;
  if (l == r) {
    lm[x] = rm[x] = l;
    sum[x] = dis[g.rin[l]];
    return;
  }
  const int mid = (l + r) >> 1;
  if (ii <= mid)
    _update(lef[x], l, mid);
  else
    _update(rig[x], mid + 1, r);
  pu(x);
}
inline void update(int& x, int i) {
  ii = i;
  _update(x, 1, N);
}
int merge(int x, int y) {
  if (!(x && y)) return x | y;
  const int r = ++tot;
  lef[r] = merge(lef[x], lef[y]);
  rig[r] = merge(rig[x], rig[y]);
  pu(r);
  return r;
}
}  // namespace itr
int rt[S];
char s[nmax];
long long ans = 2;
template <bool F>
struct _ {
  int tar[S][cmax], pre[S], len[S], too[F ? nmax : 0], seq[F ? S : 0];
  int pos[nmax];
  int lst = 1, tot = 1;
  inline int create(int l) {
    len[++tot] = l;
    return tot;
  }
  inline void insert(int p) {
    const int c = s[p];
    int i = lst;
    pos[p] = lst = create(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 = create(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 int delta() { return len[lst] - len[pre[lst]]; }
  inline void build(graph<S>& g) {
    int i;
    for (i = 2; i <= tot; i++) g.link(pre[i], i);
    g.load();
  }
  void work() {
    int i;
    const int n = len[lst];
    for (i = 1; i <= tot; i++) ++too[len[i]];
    for (i = 1; i <= n; i++) too[i] += too[i - 1];
    for (i = 1; i <= tot; i++) seq[too[len[i]]--] = i;
    for (i = tot; i; i--) {
      const int x = seq[i];
      rt[pre[x]] = itr::merge(rt[pre[x]], rt[x]);
      ans += (long long)(len[x] - len[pre[x]]) * itr::sum[rt[x]];
    }
  }
};
_<1> s1;
_<0> s2;
int n;
int main() {
  int i;
  char c;
  cin > c;
  while (c != -1 && !isspace(c)) {
    s[++n] = c - 'a';
    c = cin.get();
  }
  dis = s2.len;
  for (i = 1; i <= n; i++) {
    s1.insert(i);
    s2.insert(n - i + 1);
    if (i == n) break;
    ans += s1.delta() * 2;
    ans += s2.delta();
  }
  ans += s1.delta();
  N = s2.tot;
  s2.build(g);
  for (i = 1; i <= n - 2; i++) itr::update(rt[s1.pos[i]], g.ind[s2.pos[i + 2]]);
  s1.work();
  cout < ans < ('\n');
  return 0;
}