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;
char IO;
template <class T = int>
T rd() {
  T s = 0;
  int f = 0;
  while (!isdigit(IO = getchar())) f |= IO == '-';
  do s = (s << 1) + (s << 3) + (IO ^ '0');
  while (isdigit(IO = getchar()));
  return f ? -s : s;
}
enum { N = 100010 };
int n, m;
char s[N];
struct Suffix_Array {
  int rk[N << 1], tmp[N], cnt[N], sa[N], lcp[N];
  void Build() {
    for (int i = 1, iend = n; i <= iend; ++i) cnt[s[i] - 'a']++;
    for (int i = 1, iend = 25; i <= iend; ++i) cnt[i] += cnt[i - 1];
    for (int i = 1, iend = n; i <= iend; ++i) rk[i] = cnt[s[i] - 'a'];
    for (int i = n, iend = 1; i >= iend; --i) sa[cnt[s[i] - 'a']--] = i;
    for (int m = n, k = 1;; k <<= 1) {
      int h = 0;
      for (int i = n - k + 1, iend = n; i <= iend; ++i) tmp[++h] = i;
      for (int i = 1, iend = n; i <= iend; ++i)
        if (sa[i] > k) tmp[++h] = sa[i] - k;
      for (int i = 1, iend = n; i <= iend; ++i) cnt[rk[sa[i]]] = i;
      for (int i = n, iend = 1; i >= iend; --i) sa[cnt[rk[tmp[i]]]--] = tmp[i];
      for (int i = 1, iend = n; i <= iend; ++i)
        tmp[sa[i]] = tmp[sa[i - 1]] + (rk[sa[i]] != rk[sa[i - 1]] ||
                                       rk[sa[i - 1] + k] != rk[sa[i] + k]);
      for (int i = 1, iend = n; i <= iend; ++i) rk[i] = tmp[i];
      if ((m = rk[sa[n]]) == n) break;
    }
    int h = 0;
    for (int i = 1, iend = n; i <= iend; ++i) {
      int j = sa[rk[i] - 1];
      if (h) h--;
      while (s[i + h] == s[j + h]) h++;
      lcp[rk[i] - 1] = h;
    }
  }
};
struct LCPer : Suffix_Array {
  int st[20][N], Log[N];
  void Init() {
    for (int i = 2, iend = n; i <= iend; ++i) Log[i] = Log[i >> 1] + 1;
    for (int i = 1, iend = n; i <= iend; ++i) st[0][i] = lcp[i];
    for (int i = 1, iend = Log[n]; i <= iend; ++i) {
      int len = 1 << (i - 1);
      for (int j = 1, jend = n - len + 1; j <= jend; ++j)
        st[i][j] = min(st[i - 1][j], st[i - 1][j + len]);
    }
  }
  int LCP(int i, int j) {
    if (i == j) return n - sa[i] + 1;
    if (i > j) swap(i, j);
    j--;
    int d = Log[j - i + 1];
    return min(st[d][i], st[d][j - (1 << d) + 1]);
  }
} S;
struct SA_Solver : Suffix_Array {
  int stk[N], top, ls[N], rs[N], mk[N];
  long long ans, F[N * 2];
  set<int> st[N * 2];
  void dfs(int &u, int l, int r, int lst) {
    if (l == r) {
      u = ++m;
      int p = sa[l];
      if (p > 2) {
        int q = n - (p - 2) + 1;
        F[u] = n - q + 1;
        st[u].insert(S.rk[q]);
      }
      if (p > 1) ans += 1ll * (n - p + 1 - lst) * (F[u] + 1);
      return;
    }
    dfs(ls[u], l, u, lcp[u]), dfs(rs[u], u + 1, r, lcp[u]);
    if (st[ls[u]].size() > st[rs[u]].size()) swap(ls[u], rs[u]);
    swap(st[u], st[rs[u]]), F[u] = F[ls[u]] + F[rs[u]];
    int t = -1;
    for (int i : st[ls[u]]) {
      if (~t) F[u] += S.LCP(t, i);
      t = i;
      auto r = st[u].upper_bound(i);
      if (r != st[u].end()) F[u] -= S.LCP(i, *r);
      if (r != st[u].begin()) {
        auto l = r;
        l--;
        if (r != st[u].end()) F[u] += S.LCP(*l, *r);
        F[u] -= S.LCP(*l, i);
      }
      st[u].insert(i);
    }
    ans += 1ll * (lcp[u] - lst) * (F[u] + 1);
  }
  void Solve() {
    for (int i = 1, iend = n - 1; i <= iend; ++i) {
      while (top && lcp[stk[top]] > lcp[i]) ls[i] = stk[top--];
      if (top) rs[stk[top]] = i;
      stk[++top] = i;
    }
    for (int i = 1, iend = n - 1; i <= iend; ++i) mk[ls[i]] = mk[rs[i]] = 1;
    for (int i = 1, iend = n; i <= iend; ++i) ans += n - i + 1 - lcp[i];
    ans++;
    int lst = -1;
    for (int i = 1, iend = n; i <= iend; ++i)
      if (S.sa[i] > 1) {
        ans += n - S.sa[i] + 1;
        if (~lst)
          ans -= min(S.LCP(i, lst), min(n - S.sa[i] + 1, n - S.sa[lst] + 1));
        lst = i;
      }
    ans++;
    for (int i = 1, iend = n - 1; i <= iend; ++i)
      if (!mk[i]) dfs(i, 1, n, 0);
    printf("%lld\n", ans);
  }
} T;
int main() {
  scanf("%s", s + 1), n = m = strlen(s + 1);
  if (n == 1) return puts("3"), 0;
  T.Build(), reverse(s + 1, s + n + 1), S.Build(), S.Init();
  T.Solve();
}