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 M = 310000;
int n, m, k, a[M], id[M], sz[M], tmp[M];
set<int> s[M];
set<int>::iterator itl, itr, it;
char c[M];
long long ans, ct[M];
struct SAM {
  int c[M][26], f[M], len[M], cnt, las;
  void ins(int k, int w) {
    if (!cnt) cnt = las = 1;
    int x = ++cnt, y = las;
    las = x;
    len[x] = len[y] + 1;
    id[x] = x;
    s[x].insert(w);
    ct[x] = n - len[x];
    sz[x] = 1;
    for (; y && !c[y][k]; y = f[y]) c[y][k] = x;
    if (!y) {
      f[x] = 1;
      return;
    }
    int p = c[y][k];
    if (len[p] == len[y] + 1) {
      f[x] = p;
      return;
    }
    int np = ++cnt;
    len[np] = len[y] + 1;
    f[np] = f[p];
    f[p] = f[x] = np;
    memcpy(c[np], c[p], sizeof(c[p]));
    for (; y && c[y][k] == p; y = f[y]) c[y][k] = np;
  }
} sam;
struct SA {
  int sa[M], rk[M], px[M], cnt[M], m, h[M], st[20][M], lg[M];
  void qs() {
    for (int i = 1; i <= m; i++) cnt[i] = 0;
    for (int i = 1; i <= n; i++) cnt[rk[i]]++;
    for (int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
    for (int i = n; i >= 1; i--) sa[cnt[rk[px[i]]]--] = px[i];
  }
  void build() {
    m = 26;
    for (int i = 1; i <= n; i++) rk[i] = c[i] - 'a' + 1, px[i] = i;
    qs();
    for (int p = 0, w = 1; p < n; m = p, w <<= 1) {
      p = 0;
      for (int i = 1; i <= w; i++) px[++p] = n - w + i;
      for (int i = 1; i <= n; i++)
        if (sa[i] > w) px[++p] = sa[i] - w;
      qs();
      swap(px, rk);
      rk[sa[1]] = p = 1;
      for (int i = 2; i <= n; i++)
        rk[sa[i]] =
            (px[sa[i]] == px[sa[i - 1]] && px[sa[i] + w] == px[sa[i - 1] + w])
                ? p
                : ++p;
    }
    for (int i = 1; i <= n; i++)
      if (rk[i] != 1) {
        int t = sa[rk[i] - 1], x = max(h[rk[i - 1]] - 1, 0);
        while (c[t + x] == c[i + x]) x++;
        h[rk[i]] = x;
        st[0][rk[i]] = x;
      }
    lg[0] = -1;
    for (int i = 1; i <= n; i++) lg[i] = lg[i >> 1] + 1;
    for (int i = 1; i <= 20; i++)
      for (int j = 1; j + (1 << i) <= n + 1; j++)
        st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
  }
  int lcp(int x, int y) {
    if (x > y) swap(x, y);
    int t = lg[y - x];
    return min(st[t][x + 1], st[t][y - (1 << t) + 1]);
  }
} sa;
int mrg(int x, int y) {
  if (sz[x] < sz[y]) swap(x, y);
  if (!sz[y]) return x;
  it = s[y].begin();
  it++;
  while (it != s[y].end()) {
    s[x].insert(*it);
    itl = s[x].find(*it);
    itr = itl;
    itl--;
    itr++;
    if (itr != s[x].end()) ct[x] -= n - sa.sa[*itr] + 1 - sa.lcp(*itl, *itr);
    ct[x] += n - sa.sa[*it] + 1 - sa.lcp(*itl, *it);
    if (itr != s[x].end()) ct[x] += n - sa.sa[*itr] + 1 - sa.lcp(*it, *itr);
    it++;
  }
  sz[x] += sz[y];
  return x;
}
bool cmp(int a, int b) { return sam.len[a] > sam.len[b]; }
int main() {
  scanf("%s", c + 1);
  n = strlen(c + 1);
  if (n == 1) {
    printf("3");
    return 0;
  }
  sa.build();
  for (int i = 1; i < n; i++) sam.ins(c[i] - 'a', sa.rk[i + 2]);
  for (int i = 1; i <= sam.cnt; i++) tmp[i] = i, s[i].insert(0);
  sort(tmp + 1, tmp + 1 + sam.cnt, cmp);
  for (int i = 1; i < sam.cnt; i++) {
    int x = tmp[i];
    ans += (sam.len[x] - sam.len[sam.f[x]]) * ct[id[x]];
    id[sam.f[x]] = mrg(id[x], id[sam.f[x]]);
  }
  s[0].insert(0);
  ct[0] = n - 1;
  s[0].insert(sa.rk[2]);
  sz[0] = 1;
  id[1] = mrg(id[1], 0);
  ans += ct[id[1]];
  sam.ins(c[n] - 'a', sa.rk[n]);
  for (int i = 1; i <= sam.cnt; i++) ans += sam.len[i] - sam.len[sam.f[i]];
  printf("%lld", ans + 1);
}