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>
using namespace std;
template <typename T>
inline void read(T &x) {
  x = 0;
  char c = getchar();
  bool flag = false;
  while (!isdigit(c)) {
    if (c == '-') flag = true;
    c = getchar();
  }
  while (isdigit(c)) {
    x = (x << 1) + (x << 3) + (c ^ 48);
    c = getchar();
  }
  if (flag) x = -x;
}
int n, cnt, root = 1;
long long ans;
int id[400010], bel[400010], dfn[400010], rev[400010], dep[400010],
    st[400010][22], lg[400010];
long long sum[400010];
char str[400010];
set<int> s[400010];
int ask(int x, int y) { return dep[x] < dep[y] ? x : y; }
int lca(int x, int y) {
  x = dfn[x], y = dfn[y];
  if (x > y) swap(x, y);
  int len = lg[y - x + 1];
  return ask(st[x][len], st[y - (1 << len) + 1][len]);
}
int dis(int x, int y) {
  x = rev[x], y = rev[y];
  return dep[x] + dep[y] - 2 * dep[lca(x, y)];
}
void merge(int x, int y) {
  if (s[id[x]].size() < s[id[y]].size()) swap(id[x], id[y]);
  x = id[x], y = id[y];
  for (set<int>::iterator it = s[y].begin(); it != s[y].end(); ++it) {
    if (s[x].count(*it)) continue;
    set<int>::iterator a = s[x].insert(*it).first, b = a;
    if (a == s[x].begin())
      a = --s[x].end();
    else
      a--;
    if (++b == s[x].end()) b = s[x].begin();
    sum[x] += dis(*a, *it) + dis(*b, *it) - dis(*a, *b);
  }
}
struct SAM {
  int tot = 1, las = 1;
  int fa[400010], ch[400010][26], len[400010];
  struct edge {
    int to, nxt;
  } e[400010];
  int head[400010], edge_cnt;
  void add(int from, int to) {
    e[++edge_cnt] = {to, head[from]}, head[from] = edge_cnt;
  }
  void insert(int c) {
    int p = las, np = las = ++tot;
    len[np] = len[p] + 1;
    while (p && !ch[p][c]) ch[p][c] = np, p = fa[p];
    if (!p)
      fa[np] = root;
    else {
      int q = ch[p][c];
      if (len[q] == len[p] + 1)
        fa[np] = q;
      else {
        int nq = ++tot;
        memcpy(ch[nq], ch[q], sizeof(ch[q]));
        len[nq] = len[p] + 1, fa[nq] = fa[q], fa[q] = fa[np] = nq;
        while (ch[p][c] == q) ch[p][c] = nq, p = fa[p];
      }
    }
  }
  long long calc() {
    long long v = 0;
    for (int i = 2; i <= tot; ++i) v += len[i] - len[fa[i]];
    return v;
  }
  void dfs_get(int x) {
    dep[x] = len[x], dfn[x] = ++cnt, rev[cnt] = x, st[cnt][0] = x;
    for (int i = head[x]; i; i = e[i].nxt) dfs_get(e[i].to), st[++cnt][0] = x;
  }
  void dfs_ans(int x) {
    for (int i = head[x]; i; i = e[i].nxt) dfs_ans(e[i].to), merge(x, e[i].to);
    ans += sum[id[x]] / 2 * (len[x] - len[fa[x]]);
  }
  void workA() {
    for (int i = 2; i <= tot; ++i) add(fa[i], i);
    for (int i = 1; i <= tot; ++i) id[i] = i;
    int p = root;
    for (int i = 1; i <= n - 2; ++i) {
      p = ch[p][str[i] - 'a'];
      s[p].insert(dfn[root]), s[p].insert(dfn[bel[i + 2]]);
      sum[p] = dep[bel[i + 2]] * 2;
    }
    dfs_ans(root);
  }
  void workB() {
    for (int i = 2; i <= tot; ++i) add(fa[i], i);
    dfs_get(root);
    lg[0] = -1;
    for (int i = 1; i <= cnt; ++i) lg[i] = lg[i >> 1] + 1;
    for (int j = 1; j <= 20; ++j)
      for (int i = 1; i + (1 << j) - 1 <= cnt; ++i)
        st[i][j] = ask(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
  }
} A, B;
int main() {
  scanf("%s", str + 1), n = strlen(str + 1);
  for (int i = 1; i <= n; ++i) {
    A.insert(str[i] - 'a');
    if (i >= n - 1) ans += A.calc();
  }
  for (int i = n; i; --i) {
    B.insert(str[i] - 'a'), bel[i] = B.las;
    if (i == 2) ans += B.calc();
  }
  B.workB(), A.workA(), printf("%lld", ans + 2);
  return 0;
}