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 namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N = 100100;
const int A = 26;
const int K = 17;
const int M = (1 << 26) + 7;
unsigned char ppc[M];
int p2[N];
int sparse[K][N];
int nearLeft[N][A], nearRight[N][A];
pair<int, int> nearLeftSort[N][A], nearRightSort[N][A];
long long jumpLeft[N][K][2];
long long jumpRight[N][K][2];
long long ANS;
int n;
char s[N];
int a[N];
int curSegm[N][2];
int curIter[N];
int getMask(int l, int r) {
  int k = p2[r - l];
  return sparse[k][l] | sparse[k][r - (1 << k)];
}
void solve(int P) {
  for (int i = 0; i < n; i++) {
    if (jumpLeft[i][0][0] == 0) continue;
    int c = nearRightSort[i - 1][P - 1].second;
    jumpLeft[i][0][0] = min((int)jumpLeft[i][0][0], nearLeft[i][c]);
  }
  for (int i = 1; i <= n; i++) {
    if (jumpRight[i][0][0] == n) continue;
    int c = nearLeftSort[i][P - 1].second;
    jumpRight[i][0][0] = max((int)jumpRight[i][0][0], nearRight[i - 1][c] + 1);
  }
  for (int i = 0; i <= n; i++) {
    jumpLeft[i][0][0] = max(0, (int)jumpLeft[i][0][0]);
    jumpRight[i][0][0] = min((int)jumpRight[i][0][0], n);
    jumpLeft[i][0][1] = jumpLeft[i][0][0];
    jumpRight[i][0][1] = jumpRight[i][0][0];
  }
  for (int k = 0; k < K - 1; k++) {
    for (int i = 0; i <= n; i++) {
      int w = jumpLeft[i][k][0];
      jumpLeft[i][k + 1][0] = jumpLeft[w][k][0];
      jumpLeft[i][k + 1][1] = jumpLeft[i][k][1] + jumpLeft[w][k][1];
    }
    for (int i = 0; i <= n; i++) {
      int w = jumpRight[i][k][0];
      jumpRight[i][k + 1][0] = jumpRight[w][k][0];
      jumpRight[i][k + 1][1] = jumpRight[i][k][1] + jumpRight[w][k][1];
    }
  }
  for (int i = 0; i < n; i++) {
    int mask = getMask(curSegm[i][0], curSegm[i][1]);
    if ((int)ppc[mask] != P) continue;
    if (curIter[i] == n) continue;
    for (int k = K - 1; k >= 0; k--) {
      if (curIter[i] + (1 << k) >= n) continue;
      int l = jumpLeft[curSegm[i][0]][k][0], r = jumpRight[curSegm[i][1]][k][0];
      if ((int)ppc[getMask(l, r)] != P) continue;
      curIter[i] += 1 << k;
      ANS += jumpLeft[curSegm[i][0]][k][1];
      ANS -= jumpRight[curSegm[i][1]][k][1];
      curSegm[i][0] = l;
      curSegm[i][1] = r;
    }
    curIter[i]++;
    ANS += jumpLeft[curSegm[i][0]][0][1];
    ANS -= jumpRight[curSegm[i][1]][0][1];
    curSegm[i][0] = jumpLeft[curSegm[i][0]][0][0];
    curSegm[i][1] = jumpRight[curSegm[i][1]][0][0];
  }
}
int main() {
  for (int mask = 1; mask < M; mask++) ppc[mask] = ppc[mask >> 1] + (mask & 1);
  for (int i = 2; i < N; i++) p2[i] = p2[i / 2] + 1;
  scanf("%s", s);
  n = strlen(s);
  for (int i = 0; i < n; i++) a[i] = (int)(s[i] - 'a');
  for (int i = 0; i < n; i++) sparse[0][i] = 1 << a[i];
  for (int k = 0; k < K - 1; k++)
    for (int i = 0; i + (1 << (k + 1)) <= n; i++)
      sparse[k + 1][i] = sparse[k][i] | sparse[k][i + (1 << k)];
  for (int c = 0; c < A; c++) {
    nearLeft[0][c] = -1;
    nearRight[n - 1][c] = n;
  }
  for (int i = 1; i < n; i++) {
    for (int c = 0; c < A; c++) nearLeft[i][c] = nearLeft[i - 1][c];
    nearLeft[i][a[i - 1]] = i - 1;
  }
  for (int i = n - 2; i >= 0; i--) {
    for (int c = 0; c < A; c++) nearRight[i][c] = nearRight[i + 1][c];
    nearRight[i][a[i + 1]] = i + 1;
  }
  for (int i = 0; i < n; i++) {
    for (int c = 0; c < A; c++) {
      nearLeftSort[i][c] = make_pair(nearLeft[i][c], c);
      nearRightSort[i][c] = make_pair(nearRight[i][c], c);
    }
    sort(nearLeftSort[i], nearLeftSort[i] + A);
    reverse(nearLeftSort[i], nearLeftSort[i] + A);
    sort(nearRightSort[i], nearRightSort[i] + A);
  }
  ANS = (long long)n * n * n - n;
  for (int i = 0; i <= n; i++) {
    curSegm[i][0] = i;
    curSegm[i][1] = i + 1;
    curIter[i] = 1;
    jumpLeft[i][0][0] = i;
    jumpRight[i][0][0] = i;
  }
  for (int i = 1; i <= A; i++) solve(i);
  printf("%lld\n", ANS);
  return 0;
}