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;
namespace mine {
long long qread() {
  long long ans = 0, f = 1;
  char c = getchar();
  while (c < '0' or c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while ('0' <= c and c <= '9') ans = ans * 10 + c - '0', c = getchar();
  return ans * f;
}
void write(long long num) {
  if (num < 0) putchar('-'), num = -num;
  if (num >= 10) write(num / 10);
  putchar('0' + num % 10);
}
void write1(long long num) {
  write(num);
  putchar(' ');
}
void write2(long long num) {
  write(num);
  putchar('\n');
}
template <typename T>
inline bool chmax(T &a, const T &b) {
  return a < b ? a = b, 1 : 0;
}
template <typename T>
inline bool chmin(T &a, const T &b) {
  return a > b ? a = b, 1 : 0;
}
long long gcd(long long x, long long y) { return y ? gcd(y, x % y) : x; }
bool IN(long long x, long long l, long long r) { return l <= x and x <= r; }
const int INF = 0x3f3f3f3f;
const int MOD = 998244353;
int mm(const int x) { return x >= MOD ? x - MOD : x; }
template <typename T>
void add(T &x, const int &y) {
  x = (x + y >= MOD ? x + y - MOD : x + y);
}
long long qpower(long long x, long long e, int mod = MOD) {
  long long ans = 1;
  while (e) {
    if (e & 1) ans = ans * x % mod;
    x = x * x % mod;
    e >>= 1;
  }
  return ans;
}
long long invm(long long x) { return qpower(x, MOD - 2); }
const int N = 4e5 + 10;
int dd[N];
int dfn[N], dep[N], bak[N], dfnid;
int lg[N], stb[21][N];
int mn(int x, int y) { return dep[x] < dep[y] ? x : y; }
int ff[N][21];
vector<int> son2[N];
void dfs(int x, int fa = 0) {
  ff[x][0] = fa;
  for (int i = (1), I = (20); i <= I; i++) ff[x][i] = ff[ff[x][i - 1]][i - 1];
  dd[x] = dd[fa] + 1;
  stb[0][dfn[x] = ++dfnid] = x;
  bak[dfnid] = x;
  for (auto y : son2[x]) dfs(y), stb[0][++dfnid] = x;
}
int getlca(int x, int y) {
  if (dfn[x] > dfn[y]) swap(x, y);
  x = dfn[x], y = dfn[y];
  int t = lg[y - x + 1];
  return mn(stb[t][x], stb[t][y - (1ll << (t)) + 1]);
}
int getdis(int x, int y) { return dep[x] + dep[y] - 2 * dep[getlca(x, y)]; }
int n;
long long ans;
int go[N];
set<int> real[N];
long long realsiz[N];
vector<int> son[N];
int val[N];
void insert(int fm, int to) {
  for (auto t : real[fm]) {
    if (real[to].count(t)) continue;
    set<int>::iterator it = real[to].insert(t).first, al = it, ar = it;
    ++ar;
    if (ar == real[to].end()) ar = real[to].begin();
    if (al == real[to].begin())
      al = --real[to].end();
    else
      al--;
    int a = bak[*al], b = bak[*ar];
    realsiz[to] += getdis(a, bak[t]) + getdis(bak[t], b) - getdis(a, b);
  }
  real[fm].clear();
  realsiz[fm] = 0;
}
void dsu(int x) {
  for (auto y : son[x]) {
    dsu(y);
    if (((int)(real[go[x]]).size()) < ((int)(real[go[y]]).size()))
      insert(go[x], go[y]), swap(go[y], go[x]);
    else
      insert(go[y], go[x]);
  }
  ans += (realsiz[go[x]] / 2) * val[x];
}
char str[N];
int rev[N];
struct SAM {
  struct Nod {
    int son[26], fail, len;
  } p[N];
  int id, lst;
  SAM() { id = lst = 1; }
  int insert(int c) {
    int now = ++id;
    p[now].len = p[lst].len + 1;
    int a = lst;
    while (a and !p[a].son[c]) p[a].son[c] = now, a = p[a].fail;
    int b = p[a].son[c];
    if (!b)
      p[now].fail = 1;
    else if (p[b].len == p[a].len + 1)
      p[now].fail = b;
    else {
      int tmp = ++id;
      p[tmp] = p[b];
      p[tmp].len = p[a].len + 1;
      p[b].fail = p[now].fail = tmp;
      while (a and p[a].son[c] == b) p[a].son[c] = tmp, a = p[a].fail;
    }
    return lst = now;
  }
  void build1() {
    for (int i = (1), I = (id); i <= I; i++)
      son[p[i].fail].push_back(i), val[i] = p[i].len - p[p[i].fail].len,
                                   go[i] = i;
    for (int i = 1, now = 1; i <= n - 2; i++) {
      now = p[now].son[str[i] - 'a'];
      real[now].insert(dfn[rev[i + 2]]), real[now].insert(dfn[1]);
      realsiz[now] = dep[rev[i + 2]] * 2;
    }
    dsu(1);
  }
  void build2() {
    for (int i = (1), I = (id); i <= I; i++)
      dep[i] = p[i].len, son2[p[i].fail].push_back(i);
    dfs(1);
    for (int i = (2), I = (N - 1); i <= I; i++) lg[i] = lg[i >> 1] + 1;
    for (int t = (1), I = (20); t <= I; t++)
      for (int i = (1), I = (dfnid - (1ll << (t)) + 1); i <= I; i++)
        stb[t][i] = mn(stb[t - 1][i], stb[t - 1][i + (1ll << (t - 1))]);
  }
  long long getcnt() {
    long long ret = 0;
    for (int i = (1), I = (id); i <= I; i++) ret += p[i].len - p[p[i].fail].len;
    return ret;
  }
} A, B;
void main() {
  scanf("%s", str + 1);
  n = strlen(str + 1);
  for (int i = (1), I = (n); i <= I; i++) {
    if (i == n) ans += A.getcnt();
    A.insert(str[i] - 'a');
  }
  for (int i = (n), I = (1); i >= I; i--) {
    if (i == 1) ans += B.getcnt();
    rev[i] = B.insert(str[i] - 'a');
  }
  B.build2();
  A.build1();
  write(ans + A.getcnt() + 1 + 1);
}
};  // namespace mine
signed main() {
  srand(time(0));
  mine::main();
}