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 = 1e5 + 5, N2 = N << 1;
typedef class TrieNode {
 public:
  int len;
  TrieNode* ch[26];
  TrieNode* par;
  bool leaf;
  TrieNode() : len(0), par(NULL), leaf(false) { memset(ch, 0, sizeof(ch)); }
} TrieNode;
typedef class SuffixAutomaton {
 public:
  TrieNode pool[N << 1];
  TrieNode* _top;
  TrieNode *sam_rt, *sam_lst;
  SuffixAutomaton() : _top(pool) {
    sam_rt = newnode(0);
    sam_lst = sam_rt;
  }
  TrieNode* newnode(int len) {
    _top->len = len;
    return _top++;
  }
  int extend(int c) {
    TrieNode* cur = newnode(sam_lst->len + 1);
    TrieNode* p = sam_lst;
    while (p && !p->ch[c]) p->ch[c] = cur, p = p->par;
    if (!p) {
      cur->par = sam_rt;
    } else {
      TrieNode* q = p->ch[c];
      if (q->len == p->len + 1) {
        cur->par = q;
      } else {
        TrieNode* nq = newnode(p->len + 1);
        memcpy(nq->ch, q->ch, sizeof(q->ch));
        nq->par = q->par, q->par = nq, cur->par = nq;
        while (p && p->ch[c] == q) p->ch[c] = nq, p = p->par;
      }
    }
    sam_lst = cur;
    cur->leaf = true;
    return sam_lst - pool + 1;
  }
  int build(vector<int>* G, int* fa, int* df) {
    int K = _top - pool;
    df[1] = 1;
    for (int i = 1; i < K; i++) {
      fa[i + 1] = pool[i].par - pool + 1;
      df[i + 1] = pool[i].len + 1;
      G[fa[i + 1]].push_back(i + 1);
    }
    return K;
  }
} SuffixAutomaton;
const int bzmax = 19;
const int N4 = N2 << 1;
template <typename T>
class SparseTable {
 public:
  int n;
  int Log2[N4];
  T st[bzmax][N4];
  void init(int n, T* a) {
    Log2[0] = -1;
    for (int i = 1; i <= n; i++) {
      Log2[i] = Log2[i >> 1] + 1;
    }
    for (int i = 1; i <= n; i++) {
      st[0][i] = a[i];
    }
    for (int i = 1; i < bzmax; i++) {
      for (int j = 1; j + (1 << i) - 1 <= n; j++) {
        st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
      }
    }
  }
  T query(int l, int r) {
    int b = Log2[r - l + 1];
    return min(st[b][l], st[b][r - (1 << b) + 1]);
  }
};
typedef class Tree {
 public:
  int n;
  int dfc;
  int dep[N2];
  pair<int, int> seq[N4];
  vector<int>* G;
  int in[N2], out[N2];
  SparseTable<pair<int, int> > st;
  void dfs1(int p, int fa) {
    in[p] = ++dfc;
    dep[p] = dep[fa] + 1;
    seq[dfc] = pair<int, int>(dep[p], p);
    for (auto e : G[p]) {
      if (e ^ fa) {
        dfs1(e, p);
        seq[++dfc] = pair<int, int>(dep[p], p);
      }
    }
    out[p] = dfc;
  }
  int _lca(int l, int r) { return st.query(l, r).second; }
  int lca(int u, int v) {
    (in[u] > in[v]) && (swap(u, v), 0);
    return _lca(in[u], in[v]);
  }
  void init(int n, vector<int>* G) {
    this->G = G;
    this->n = n;
    dfc = 0;
    dfs1(1, 0);
    st.init(dfc, seq);
  }
} Tree;
vector<int> G1[N2];
int fa1[N2], df1[N2];
Tree tr;
vector<int> G2[N2];
int fa2[N2], df2[N2];
int dfc;
int in[N2], tour[N2];
void dfs(int p) {
  in[p] = ++dfc;
  tour[in[p]] = p;
  for (auto e : G2[p]) {
    if (e ^ fa2[p]) {
      dfs(e);
    }
  }
}
typedef class VirtualTree {
 public:
  long long res;
  set<int> S;
  int get_pre(int x) {
    set<int>::iterator it = S.lower_bound(x);
    if (it == S.begin()) return -1;
    return *--it;
  }
  int get_suf(int x) {
    set<int>::iterator it = S.upper_bound(x);
    if (it == S.end()) return -1;
    return *it;
  }
  void insert(int p);
  int size() { return S.size(); }
} VirtualTree;
void VirtualTree::insert(int p) {
  int x = in[p];
  int l = get_pre(x), r = get_suf(x);
  res += df2[p];
  if (l != -1 && r != -1) {
    int g = tr.lca(tour[l], tour[r]);
    res += df2[g];
  }
  if (l != -1) {
    int g = tr.lca(tour[l], p);
    res -= df2[g];
  }
  if (r != -1) {
    int g = tr.lca(p, tour[r]);
    res -= df2[g];
  }
  S.insert(x);
}
int n;
long long ans = 0;
char s[N];
VirtualTree vt[N2];
int id1[N], id2[N];
SuffixAutomaton saml, samr;
void merge(VirtualTree& a, VirtualTree& b) {
  if (a.size() < b.size()) swap(a, b);
  for (auto x : b.S) {
    a.insert(tour[x]);
  }
}
void solve(int p) {
  for (auto e : G1[p]) {
    solve(e);
    merge(vt[p], vt[e]);
  }
  ans += (df1[p] - df1[fa1[p]]) * (vt[p].res + 1);
}
int main() {
  scanf("%s", s + 1);
  n = strlen(s + 1);
  id1[0] = 1;
  for (int i = 1; i <= n; i++) {
    id1[i] = saml.extend(s[i] - 'a');
  }
  id2[n + 1] = 1;
  for (int i = n; i; i--) {
    id2[i] = samr.extend(s[i] - 'a');
  }
  saml.build(G1, fa1, df1);
  tr.init(samr.build(G2, fa2, df2), G2);
  dfs(1);
  for (int i = 0; i < n; i++) {
    vt[id1[i]].insert(id2[i + 2]);
  }
  solve(1);
  printf("%lld\n", ans);
  return 0;
}