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>
int N, a[100002], pre[100002][26], suc[100002][26];
long long O;
char _in[100002];
int JL[27][100002], JR[27][100002], LOG;
int curl[100001], curr[100001], cc[100001];
int PL[17][100002], PR[17][100002];
long long SL[17][100002], SR[17][100002];
int main() {
  scanf("%s", _in + 1);
  while (_in[N + 1]) N++;
  for (int i = 1; i <= N; i++) a[i] = _in[i] - 'a';
  for (int i = 2; i <= N + 1; i++) {
    for (int j = 0; j < 26; j++) pre[i][j] = pre[i - 1][j];
    pre[i][a[i - 1]] = i - 1;
  }
  for (int i = 0; i < 26; i++) suc[N][i] = N + 1;
  for (int i = N - 1; i >= 0; i--) {
    for (int j = 0; j < 26; j++) suc[i][j] = suc[i + 1][j];
    suc[i][a[i + 1]] = i + 1;
  }
  for (int i = 1; i <= N; i++) {
    static int g[27];
    int L = 0;
    for (int j = 0; j < 26; j++)
      if (suc[i - 1][j] != N + 1) g[++L] = j;
    std::sort(g + 1, g + L + 1,
              [i](int x, int y) { return suc[i - 1][x] < suc[i - 1][y]; });
    for (int j = 1, w = i; j <= L; j++)
      JL[j][i] = w = std::min(w, std::max(1, pre[i][g[j]]));
    for (int j = L + 1; j <= 26; j++) JL[j][i] = -1;
    L = 0;
    for (int j = 0; j < 26; j++)
      if (pre[i + 1][j] != 0) g[++L] = j;
    std::sort(g + 1, g + L + 1,
              [i](int x, int y) { return pre[i + 1][x] > pre[i + 1][y]; });
    for (int j = 1, w = i; j <= L; j++)
      JR[j][i] = w = std::max(w, std::min(N, suc[i][g[j]]));
    for (int j = L + 1; j <= 26; j++) JR[j][i] = -1;
  }
  while (2 << LOG <= N) LOG++;
  for (int i = 1; i <= N; i++) {
    curl[i] = curr[i] = i;
    cc[i] = 1;
  }
  for (int C = 1; C <= 26; C++) {
    for (int i = 1; i <= N; i++) {
      PL[0][i] = JL[C][i];
      PR[0][i] = JR[C][i];
      if (~PL[0][i]) SL[0][i] = i - 1;
      if (~PR[0][i]) SR[0][i] = N - i;
    }
    for (int i = 1; i <= LOG; i++)
      for (int j = 1; j <= N; j++) {
        if (~PL[i - 1][j]) {
          PL[i][j] = PL[i - 1][PL[i - 1][j]];
          if (~PL[i][j]) SL[i][j] = SL[i - 1][j] + SL[i - 1][PL[i - 1][j]];
        } else
          PL[i][j] = -1;
        if (~PR[i - 1][j]) {
          PR[i][j] = PR[i - 1][PR[i - 1][j]];
          if (~PR[i][j]) SR[i][j] = SR[i - 1][j] + SR[i - 1][PR[i - 1][j]];
        } else
          PR[i][j] = -1;
      }
    for (int i = 1; i <= N; i++)
      if (cc[i] == C && (curl[i] > 1 || curr[i] < N)) {
        int L_lim = 0, R_lim = N + 1;
        for (int j = 0; j < 26; j++)
          if (pre[curr[i] + 1][j] < curl[i]) {
            L_lim = std::max(L_lim, pre[curl[i]][j]);
            R_lim = std::min(R_lim, suc[curr[i]][j]);
          }
        for (int j = LOG; j >= 0; j--)
          if (~PL[j][curl[i]] && PL[j][curl[i]] > L_lim && ~PR[j][curr[i]] &&
              PR[j][curr[i]] < R_lim) {
            O += SL[j][curl[i]] + SR[j][curr[i]];
            curl[i] = PL[j][curl[i]];
            curr[i] = PR[j][curr[i]];
          }
        if (~PL[0][curl[i]] && ~PR[0][curr[i]]) {
          O += curl[i] - 1 + N - curr[i];
          curl[i] = PL[0][curl[i]];
          curr[i] = PR[0][curr[i]];
        }
        cc[i] = 0;
        for (int j = 0; j < 26; j++)
          if (pre[curr[i] + 1][j] >= curl[i]) cc[i]++;
      }
  }
  printf("%lld\n", O);
  return 0;
}