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>
template <class T1, class T2>
inline bool cmin(T1 &a, const T2 &b) {
  return b < a ? (a = b, true) : false;
}
template <class T1, class T2>
inline bool cmax(T1 &a, const T2 &b) {
  return a < b ? (a = b, true) : false;
}
const int N = 1e5 + 5;
int n, last[26], l[N], r[N], pre[N][27], nex[N][27], f[N][27], g[N][27],
    curl[N], curr[N], flift[17][N], glift[17][N];
char s[N];
long long fsum[17][N], gsum[17][N];
int main() {
  assert(scanf("%s", s) == 1);
  n = strlen(s);
  for (int i = 0; i < n; ++i) s[i] -= 'a';
  for (int i = 0; i < n; ++i) {
    l[i] = last[s[i]];
    last[s[i]] = i;
    memcpy(pre[i], last, sizeof(last));
    std::sort(pre[i], pre[i] + 26, std::greater<int>());
    pre[i][26] = -1;
  }
  for (int i = 0; i < 26; ++i) last[i] = n - 1;
  for (int i = n; i--;) {
    r[i] = last[s[i]];
    last[s[i]] = i;
    memcpy(nex[i], last, sizeof(last));
    std::sort(nex[i], nex[i] + 26);
    nex[i][26] = n;
  }
  for (int i = 0; i < n; ++i) {
    curl[i] = curr[i] = i;
    f[i][0] = g[i][0] = i;
    for (int j = 0; j < 26; ++j) {
      f[i][j + 1] = std::min(f[i][j], l[nex[i][j]]);
      g[i][j + 1] = std::max(g[i][j], r[pre[i][j]]);
    }
  }
  long long ans = 0;
  for (int t = 1; t <= 26; ++t) {
    for (int i = 0; i < n; ++i) {
      flift[0][i] = f[i][t];
      glift[0][i] = g[i][t];
      fsum[0][i] = gsum[0][i] = i;
    }
    for (int i = 1; (1 << i) <= n; ++i)
      for (int j = 0; j < n; ++j) {
        flift[i][j] = flift[i - 1][flift[i - 1][j]];
        glift[i][j] = glift[i - 1][glift[i - 1][j]];
        fsum[i][j] = fsum[i - 1][j] + fsum[i - 1][flift[i - 1][j]];
        gsum[i][j] = gsum[i - 1][j] + gsum[i - 1][glift[i - 1][j]];
      }
    for (int i = 0; i < n; ++i) {
      for (int j = 31 - __builtin_clz(n); j >= 0; --j) {
        int nexl = flift[j][curl[i]], nexr = glift[j][curr[i]];
        if (nexr < nex[nexl][t]) {
          ans += ((n - 1ll) << j) + fsum[j][curl[i]] - gsum[j][curr[i]];
          curl[i] = nexl, curr[i] = nexr;
        }
      }
      if (curr[i] < nex[curl[i]][t]) {
        ans += n - 1 + curl[i] - curr[i];
        curl[i] = f[curl[i]][t];
        curr[i] = g[curr[i]][t];
      }
    }
  }
  printf("%lld\n", ans);
  return 0;
}