Problem: There is a string s of lowercase English letters. A cursor is positioned on one of the characters. The cursor can be moved with the following operation: choose a letter c and a direction (left or right). The cursor is then moved to the closest occurence of c in the chosen direction. If there is no letter c in that direction, the cursor stays in place. For example, if s = abaab with the cursor on the second character (a[b]aab), then:

  * moving to the closest letter a to the left places the cursor on the first character ([a]baab);
  * moving to the closest letter a to the right places the cursor the third character (ab[a]ab);
  * moving to the closest letter b to the right places the cursor on the fifth character (abaa[b]);
  * any other operation leaves the cursor in place.



Let dist(i, j) be the smallest number of operations needed to move the cursor from the i-th character to the j-th character. Compute \displaystyle ∑_{i = 1}^n ∑_{j = 1}^n dist(i, j).

Input

The only line contains a non-empty string s of at most 10^5 lowercase English letters.

Output

Print a single integer \displaystyle ∑_{i = 1}^n ∑_{j = 1}^n dist(i, j).

Examples

Input


abcde


Output


20


Input


abacaba


Output


58

Note

In the first sample case, dist(i, j) = 0 for any pair i = j, and 1 for all other pairs.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using ll = long long;
const int MN = 1e5 + 100;
const int CH = 26;
const int NL = 18;
ll F;
int s[MN], N;
int c[MN][CH], n[2][MN][CH], m[2][MN][CH];
int a[CH];
int get(int a, int b) {
  ++b;
  int r = 0;
  for (int i = 0; i < CH; ++i)
    if (c[b][i] > c[a][i]) r |= 1 << i;
  return r;
}
struct SEG {
 public:
  SEG(int n = -1, ll c = -1LL) : n(n), c(c) {}
  int n;
  ll c;
};
SEG l[MN][NL], r[MN][NL];
int L[MN], R[MN];
int main(void) {
  for (char t; scanf(" %c", &t) != EOF;)
    if (t != '\n') s[N++] = t - 'a';
  for (int i = 0; i < CH; ++i) n[1][0][i] = -1, n[0][N - 1][i] = N;
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < CH; ++j)
      c[i + 1][j] = c[i][j], n[1][i + 1][j] = n[1][i][j];
    ++c[i + 1][s[i]];
    n[1][i + 1][s[i]] = i;
  }
  for (int i = N - 1; i > 0; --i) {
    for (int j = 0; j < CH; ++j) n[0][i - 1][j] = n[0][i][j];
    n[0][i - 1][s[i]] = i;
  }
  for (int i = 0, *q; i < N; ++i) {
    a[0] = s[i];
    for (int j = 0; j < CH - 1; ++j) a[j + 1] = j + (j >= s[i]);
    q = n[0][i];
    std::sort(a + 1, a + CH, [&](int x, int y) {
      return q[x] < q[y] || !(q[y] < q[x]) && x < y;
    });
    for (int j = 0, T = N; j < CH; ++j) {
      if (!j || q[a[j]] < N) T = std::min(T, std::max(0, n[1][i][a[j]]));
      m[1][i][j] = T;
    }
    q = n[1][i];
    std::sort(a + 1, a + CH, [&](int x, int y) {
      return q[x] > q[y] || !(q[y] > q[x]) && x < y;
    });
    for (int j = 0, T = 0; j < CH; ++j) {
      if (!j || q[a[j]] >= 0) T = std::max(T, std::min(N - 1, n[0][i][a[j]]));
      m[0][i][j] = T;
    }
  }
  for (int i = 0; i < NL; ++i) l[0][i] = {0, 0LL}, r[N - 1][i] = {N - 1, 0LL};
  for (int i = 0; i < N; ++i) L[i] = R[i] = i;
  for (int i = 0, m, ml, mr; i < CH; ++i) {
    for (int j = 1; j < N; ++j) {
      l[j][0] = {::m[1][j][i], static_cast<ll>(j)};
      for (int k = 0; k + 1 < NL; ++k)
        l[j][k + 1] = {l[l[j][k].n][k].n, l[j][k].c + l[l[j][k].n][k].c};
    }
    for (int j = N - 2; j >= 0; --j) {
      r[j][0] = {::m[0][j][i], static_cast<ll>(N - j - 1)};
      for (int k = 0; k + 1 < NL; ++k)
        r[j][k + 1] = {r[r[j][k].n][k].n, r[j][k].c + r[r[j][k].n][k].c};
    }
    for (int j = 0; j < N; ++j)
      if (L[j] > 0 || R[j] < N - 1) {
        int C = get(L[j], R[j]);
        if (__builtin_popcount(C) > i + 1) continue;
        ml = mr = 0;
        for (int k = NL - 1, t = L[j], u; k >= 0; --k)
          if ((get(u = l[t][k].n, L[j]) | C) == C) t = u, ml |= 1 << k;
        for (int k = NL - 1, t = R[j], u; k >= 0; --k)
          if ((get(R[j], u = r[t][k].n) | C) == C) t = u, mr |= 1 << k;
        m = std::min(ml, mr);
        if (m + 1 < 1 << NL) ++m;
        for (int k = 0; 1 << k <= m; ++k)
          if (m & 1 << k)
            F += r[R[j]][k].c + l[L[j]][k].c, R[j] = r[R[j]][k].n,
                                              L[j] = l[L[j]][k].n;
      }
  }
  printf("%lld\n", F);
  return 0;
}