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 = 250000;
long long tmpans, ans;
int tottime;
struct SAM {
  struct Node {
    int len, fa, ch[26];
  } a[N];
  int node_cnt, cur;
  vector<int> e[N];
  void ade(int u, int v) { e[u].push_back(v); }
  void clear() { node_cnt = cur = 1; }
  void ins(int ch) {
    int u = cur;
    cur = ++node_cnt;
    a[cur].len = a[u].len + 1;
    for (; u && !a[u].ch[ch]; u = a[u].fa) a[u].ch[ch] = cur;
    if (!u) {
      a[cur].fa = 1;
      tmpans += a[cur].len;
      return;
    }
    int v = a[u].ch[ch];
    if (a[v].len == a[u].len + 1) {
      a[cur].fa = v;
      tmpans += a[cur].len - a[v].len;
      return;
    }
    int t = ++node_cnt;
    a[t] = a[v], a[t].len = a[u].len + 1;
    a[v].fa = a[cur].fa = t;
    for (; u && a[u].ch[ch] == v; u = a[u].fa) a[u].ch[ch] = t;
    tmpans += a[cur].len - a[t].len;
  }
  void build() {
    for (int i = 2; i <= node_cnt; i++) ade(a[i].fa, i);
  }
  void print() {
    for (int i = 1; i <= node_cnt; i++) printf("%d %d\n", i, a[i].fa);
  }
} s1, s2;
int tn, can[N], nid1[N], size[N], dfn1[N], son[N], root[N], seg_cnt,
    ch[N * 20][2], dfs_cnt, euler_cnt, euler[20][N << 1], edfn[N], dfn[N],
    nid[N], pos1[N], pos2[N], dep[N], lg[N << 1];
char st[N];
struct TNode {
  int u, dfn;
  bool operator<(const TNode &a) const { return dfn < a.dfn; }
} tmp[N * 20];
void dfs2(int u) {
  dfn[u] = ++dfs_cnt;
  nid[dfs_cnt] = u;
  dep[u] = dep[s2.a[u].fa] + 1;
  euler[0][++euler_cnt] = u;
  edfn[u] = euler_cnt;
  for (vector<int>::iterator i = s2.e[u].begin(); i != s2.e[u].end(); i++) {
    int v = *i;
    dfs2(v);
    euler[0][++euler_cnt] = u;
  }
}
void make() {
  lg[0] = -1;
  for (int i = 1; i <= euler_cnt; i++) lg[i] = lg[i >> 1] + 1;
  for (int i = 1; (1 << i) <= euler_cnt; i++)
    for (int j = 1; j + (1 << i) - 1 <= euler_cnt; j++) {
      int x = euler[i - 1][j], y = euler[i - 1][j + (1 << (i - 1))];
      euler[i][j] = dep[x] < dep[y] ? x : y;
    }
}
int lca(int u, int v) {
  clock_t begt = clock();
  u = edfn[u], v = edfn[v];
  if (u > v) swap(u, v);
  int len = lg[v - u + 1];
  int x = euler[len][u], y = euler[len][v - (1 << len) + 1];
  tottime += clock() - begt;
  return dep[x] < dep[y] ? x : y;
}
set<TNode> S;
void ins(int u) {
  TNode t = {u, dfn[u]};
  set<TNode>::iterator pre = --S.lower_bound(t), suc = S.upper_bound(t);
  if (pre->u && suc->u != s2.node_cnt + 1)
    tmpans += s2.a[lca(pre->u, suc->u)].len;
  tmpans += s2.a[u].len;
  if (pre->u) tmpans -= s2.a[lca(pre->u, u)].len;
  if (suc->u != s2.node_cnt + 1) tmpans -= s2.a[lca(suc->u, u)].len;
  S.insert(t);
}
void dfs1(int u, int flag) {
  dfn1[u] = ++dfs_cnt;
  nid1[dfs_cnt] = u;
  for (vector<int>::iterator i = s1.e[u].begin(); i != s1.e[u].end(); i++) {
    int v = *i;
    if (v == son[u]) continue;
    dfs1(v, 0);
  }
  long long tmps = tmpans;
  if (son[u]) dfs1(son[u], 1);
  for (int i = dfn1[u]; i <= dfn1[u] + size[u] - size[son[u]] - 1; i++)
    if (can[nid1[i]]) ins(can[nid1[i]]);
  ans += 1ll * (s1.a[u].len - s1.a[s1.a[u].fa].len) * tmpans;
  if (!flag) {
    tmpans = tmps;
    S.clear();
    S.insert((TNode){0, 0}),
        S.insert((TNode){s2.node_cnt + 1, s2.node_cnt + 1});
  }
}
void dfs3(int u) {
  size[u] = 1;
  int mx = 0;
  for (vector<int>::iterator i = s1.e[u].begin(); i != s1.e[u].end(); i++) {
    int v = *i;
    dfs3(v);
    size[u] += size[v];
    if (size[v] > mx) mx = size[v], son[u] = v;
  }
}
int main() {
  scanf("%s", st + 1);
  s1.clear(), s2.clear();
  int n = strlen(st + 1);
  for (int i = 1; i < n; i++) s1.ins(st[i] - 97), pos1[i] = s1.cur;
  ans += tmpans;
  s1.ins(st[n] - 97);
  ans += tmpans;
  tmpans = 0;
  for (int i = n; i > 1; i--) s2.ins(st[i] - 97), pos2[i] = s2.cur;
  ans += tmpans;
  s2.ins(st[1] - 97);
  ans++;
  ans++;
  tmpans = 0;
  s1.build(), s2.build();
  dfs2(1);
  make();
  for (int i = 1; i <= n - 2; i++) can[pos1[i]] = pos2[i + 2];
  dfs3(1), dfs_cnt = 0, S.insert((TNode){0, 0}),
           S.insert((TNode){s2.node_cnt + 1, s2.node_cnt + 1});
  dfs1(1, 1);
  cout << ans << endl;
}