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 CN = 2e5 + 10;
long long ans = 2, sum[CN];
int ps[CN], cnt[CN], id[CN];
class SUF {
 public:
  int id, dfn;
  bool operator<(const SUF &o) const { return dfn < o.dfn; }
};
SUF mk(int a, int b) {
  SUF o;
  o.id = a, o.dfn = b;
  return o;
}
set<SUF> ed[CN];
int n, dfx, dfn[CN], vis[CN], lg[CN << 1], mn[20][CN << 1];
char ch[CN];
vector<int> G[CN];
int LCP(int l, int r) {
  l = dfn[l], r = dfn[r];
  if (l > r) swap(l, r);
  int e = lg[r - l + 1];
  return min(mn[e][l], mn[e][r - (1 << e) + 1]);
}
class SAM {
 public:
  int son[CN][26], nxt[CN], len[CN], idx, lst;
  SAM() { nxt[0] = -1; }
  void et(int c) {
    int u = ++idx, p = lst;
    lst = u, len[u] = len[p] + 1;
    while (p ^ -1 && !son[p][c]) son[p][c] = u, p = nxt[p];
    if (p == -1) return;
    int d = son[p][c];
    if (len[d] == len[p] + 1) return (void)(nxt[u] = d);
    int v = ++idx;
    len[v] = len[p] + 1, nxt[v] = nxt[d], nxt[d] = nxt[u] = v;
    memcpy(son[v], son[d], sizeof(son[d]));
    while (p ^ -1 && son[p][c] == d) son[p][c] = v, p = nxt[p];
  }
  void bd() {
    for (int i = 1; i <= idx; i++) G[nxt[i]].push_back(i);
  }
  void dfs(int u) {
    mn[0][++dfx] = len[u];
    if (vis[u]) dfn[vis[u]] = dfx;
    for (int l = G[u].size(), i = 0; i < l; i++) {
      int v = G[u][i];
      dfs(v), mn[0][++dfx] = len[u];
    }
  }
  void work() {
    for (int i = 1; i <= n - 2; i++)
      ed[ps[i]].insert(mk(i + 2, dfn[i + 2])), sum[ps[i]] = n - i - 1;
    for (int i = 1; i <= idx; i++) cnt[len[i]]++;
    for (int i = n; i; i--) cnt[i] += cnt[i + 1];
    for (int i = 1; i <= idx; i++) id[cnt[len[i]]--] = i;
    for (int p = 1, i; i = id[p], p <= idx; p++) {
      ans += sum[i] * (len[i] - len[nxt[i]]);
      if (!nxt[i]) continue;
      int v = nxt[i];
      if (!ed[v].size()) {
        ed[v] = ed[i], sum[v] = sum[i];
        continue;
      }
      if (ed[v].size() < ed[i].size()) swap(ed[v], ed[i]), swap(sum[v], sum[i]);
      for (set<SUF>::iterator it = ed[i].begin(); it != ed[i].end(); it++) {
        set<SUF>::iterator L = ed[v].lower_bound(*it), R = L;
        if (L == ed[v].begin())
          sum[v] -= LCP((*it).id, (*L).id);
        else {
          L--;
          if (R == ed[v].end())
            sum[v] -= LCP((*it).id, (*L).id);
          else
            sum[v] += LCP((*L).id, (*R).id) - LCP((*L).id, (*it).id) -
                      LCP((*R).id, (*it).id);
        }
        sum[v] += n - (*it).id + 1, ed[v].insert(*it);
      }
    }
  }
} P, S;
int main() {
  for (int i = 2; i <= 400000; i++) lg[i] = lg[i >> 1] + 1;
  scanf("%s", ch + 1), n = strlen(ch + 1);
  for (int i = 1; i <= n; i++)
    P.et(ch[i] - 'a'),
        ps[i] = P.lst,
        ans += i < n ? 2 * (i - P.len[P.nxt[P.lst]]) : i - P.len[P.nxt[P.lst]];
  for (int i = n; i; i--)
    S.et(ch[i] - 'a'), vis[S.lst] = i,
                       ans += i > 1 ? n - i + 1 - S.len[S.nxt[S.lst]] : 0;
  S.bd(), S.dfs(0);
  for (int k = 0; k < 19; k++)
    for (int i = 1; i + (1 << k) <= dfx; i++)
      mn[k + 1][i] = min(mn[k][i], mn[k][i + (1 << k)]);
  return P.work(), printf("%lld\n", ans), 0;
}