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;
const int N = 200005, C = 26, L = 19, M = N * 30;
using ll = long long;
int n;
char s[N];
ll ans;
int st[N], mn[L][N << 1], dep[N], lg[N << 1];
int lca(int x, int y) {
  if (!x || !y) return 0;
  if (x > y) swap(x, y);
  int k = lg[y - x + 1];
  return dep[mn[k][x]] < dep[mn[k][y - (1 << k) + 1]] ? mn[k][x]
                                                      : mn[k][y - (1 << k) + 1];
}
int rt[N], lc[M], rc[M], ml[M], mr[M], idx, tidx;
ll sm[M];
void pushup(int pos) {
  sm[pos] = sm[lc[pos]] + sm[rc[pos]] - dep[lca(ml[rc[pos]], mr[lc[pos]])];
  ml[pos] = ml[lc[pos]] ? ml[lc[pos]] : ml[rc[pos]];
  mr[pos] = mr[rc[pos]] ? mr[rc[pos]] : mr[lc[pos]];
}
void modify(int &pos, int l, int r, int p) {
  if (!pos) pos = ++idx;
  if (l == r) {
    ml[pos] = mr[pos] = p;
    sm[pos] = dep[mn[0][p]];
    return;
  }
  int mid = (l + r) >> 1;
  if (p <= mid)
    modify(lc[pos], l, mid, p);
  else
    modify(rc[pos], mid + 1, r, p);
  pushup(pos);
}
void merge(int &pos, int l, int r) {
  if (!l || !r) {
    pos = l | r;
    return;
  }
  pos = ++idx;
  assert(lc[l] || rc[l]);
  merge(lc[pos], lc[l], lc[r]);
  merge(rc[pos], rc[l], rc[r]);
  pushup(pos);
}
struct SAM {
  int t[N][C], fa[N], len[N], pos[N], idx, lst;
  vector<int> v[N];
  SAM() {
    fa[0] = -1;
    len[0] = idx = lst = 0;
  }
  void ins(int c) {
    int pos = ++idx, p = lst, q;
    len[lst = pos] = len[p] + 1;
    while (p != -1 && !t[p][c]) t[p][c] = pos, p = fa[p];
    if (p == -1)
      fa[pos] = 0;
    else if (len[q = t[p][c]] == len[p] + 1)
      fa[pos] = q;
    else {
      int cl = ++idx;
      memcpy(t[cl], t[q], sizeof(t[cl]));
      fa[cl] = fa[q];
      len[cl] = len[p] + 1;
      while (p != -1 && t[p][c] == q) t[p][c] = cl, p = fa[p];
      fa[pos] = fa[q] = cl;
    }
  }
  void dfs(int pos) {
    mn[0][st[pos] = ++tidx] = pos;
    for (auto &i : v[pos]) {
      dep[i] = dep[pos] + len[i] - len[pos];
      dfs(i);
      mn[0][++tidx] = pos;
    }
  }
  void dfs2(int pos) {
    for (auto &i : v[pos]) dfs2(i), merge(rt[pos], rt[pos], rt[i]);
  }
  void buildr() {
    for (int i = 1; i <= idx; i++) v[fa[i]].push_back(i);
    dfs(0);
    for (int j = 1; j < L; j++)
      for (int i = 1; i <= tidx - (1 << j) + 1; i++)
        mn[j][i] = dep[mn[j - 1][i]] < dep[mn[j - 1][i + (1 << (j - 1))]]
                       ? mn[j - 1][i]
                       : mn[j - 1][i + (1 << (j - 1))];
    for (int i = 2; i <= tidx; i++) lg[i] = lg[i >> 1] + 1;
  }
  void builds() {
    for (int i = 1; i <= idx; i++) v[fa[i]].push_back(i);
    dfs2(0);
    for (int i = 1; i <= idx; i++) ans += ll(len[i] - len[fa[i]]) * sm[rt[i]];
  }
} sa, ra;
int main() {
  ios::sync_with_stdio(false);
  cin >> s;
  n = strlen(s);
  for (int i = 0; i < n; i++) {
    sa.ins(s[i] - 'a'), sa.pos[i] = sa.lst;
    ans += (i + 1) - sa.len[sa.fa[sa.lst]];
    if (i == n - 2) ans *= 2;
  }
  for (int i = n - 1; i >= 0; --i) {
    ra.ins(s[i] - 'a'), ra.pos[i] = ra.lst;
    if (i > 0) ans += ra.len[ra.lst] - ra.len[ra.fa[ra.lst]];
  }
  ans += 2;
  ra.buildr();
  for (int i = 0; i < n - 2; i++)
    modify(rt[sa.pos[i]], 1, tidx, st[ra.pos[i + 2]]);
  sa.builds();
  cout << ans << endl;
  return 0;
}