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;
const int N = 1e5 + 5;
int a1[N][30], a2[N][30], le1[N], le2[N], lst[30], lstt[30];
int n, i, j, k, l, x, y;
char c[N];
int lb[N], rb[N], lcha[N], rcha[N], ct[N], stp[N];
bool bb[N][30];
int dl[N], dr[N], fl[20][N], fr[20][N];
long long sl[N], sr[N], ss[N], ans;
inline void fix(int i) {
  for (; lcha[i] < le1[i] && bb[i][c[a1[i][lcha[i]]] - 'a']; ++lcha[i])
    ;
  for (; rcha[i] < le2[i] && bb[i][c[a2[i][rcha[i]]] - 'a']; ++rcha[i])
    ;
}
inline void fix2(int i) {
  int j;
  for (j = 0; j < le1[i] && a1[i][j] >= lb[i]; ++j) {
    bool& b = bb[i][c[a1[i][j]] - 'a'];
    if (!b) ++ct[i], b = 1;
  }
  for (j = 0; j < le2[i] && a2[i][j] <= rb[i]; ++j) {
    bool& b = bb[i][c[a2[i][j]] - 'a'];
    if (!b) ++ct[i], b = 1;
  }
  fix(i);
}
int main() {
  scanf("%s", c + 1);
  n = strlen(c + 1);
  for (i = 1; i <= n; ++i) {
    for (j = 0; j < 26; ++j)
      if (lst[j]) a1[i][le1[i]++] = lst[j];
    sort(a1[i], a1[i] + le1[i], greater<int>());
    lst[c[i] - 'a'] = i;
  }
  memcpy(lstt, lst, 104);
  memset(lst, 0, 104);
  for (i = n; i; --i) {
    for (j = 0; j < 26; ++j)
      if (lst[j]) a2[i][le2[i]++] = lst[j];
    sort(a2[i], a2[i] + le2[i]);
    lst[c[i] - 'a'] = i;
  }
  for (i = 1; i <= n; ++i)
    lcha[i] = rcha[i] = 0, ct[i] = 1, bb[i][c[i] - 'a'] = 1, fix(i),
    lb[i] = rb[i] = i;
  for (i = 1; i <= 26; ++i) {
    for (j = 1; j <= n; ++j)
      dl[j] = dl[fl[0][j] = a1[j][i - 1]] + 1, sl[j] = sl[fl[0][j]] + j;
    for (j = n; j; --j)
      dr[j] = dr[fr[0][j] = a2[j][i - 1]] + 1, sr[j] = sr[fr[0][j]] + j;
    for (k = 1; k < 20; ++k)
      for (j = 1; j <= n; ++j)
        fl[k][j] = fl[k - 1][fl[k - 1][j]], fr[k][j] = fr[k - 1][fr[k - 1][j]];
    for (j = 1; j <= n; ++j)
      if (ct[j] == i && (lb[j] > 1 || rb[j] < n)) {
        int ld = 0, rd = 0, d, x = lb[j], y = rb[j],
            l = lcha[j] < le1[j] ? a1[j][lcha[j]] : 0,
            r = rcha[j] < le2[j] ? a2[j][rcha[j]] : n + 1;
        for (k = 19; k >= 0; --k)
          if (fl[k][x] > l) x = fl[k][x];
        ld = dl[lb[j]] - dl[x];
        for (k = 19; k >= 0; --k)
          if (fr[k][y] && fr[k][y] < r) y = fr[k][y];
        rd = dr[rb[j]] - dr[y];
        if (l == 0 && r == n + 1)
          d = max(ld, rd);
        else if (l == 0)
          d = rd;
        else if (r == n + 1)
          d = ld;
        else
          d = min(ld, rd);
        if (ld > d && r <= n)
          for (x = lb[j], ld = d, k = 19; k >= 0; --k)
            if (rd >> k & 1) x = fl[k][x];
        if (rd > d && 0 < l)
          for (y = rb[j], rd = d, k = 19; k >= 0; --k)
            if (ld >> k & 1) y = fr[k][y];
        ss[j] += (sr[rb[j]] - sr[fr[0][y]] + 1ll * (d - rd) * n) -
                 (sl[lb[j]] - sl[fl[0][x]] + d - ld) + (d + 1);
        for (k = 0; k < 26; ++k)
          if (bb[j][k] && lst[k] >= x) break;
        if (k == 26) {
          for (k = le1[x] - 1; k >= 0 && !bb[j][c[a1[x][k]] - 'a']; --k)
            ;
          lb[j] = k >= 0 ? a1[x][k] : 1;
        } else
          lb[j] = 1;
        for (k = 0; k < 26; ++k)
          if (bb[j][k] && lstt[k] <= y) break;
        if (k == 26) {
          for (k = le2[y] - 1; k >= 0 && !bb[j][c[a2[y][k]] - 'a']; --k)
            ;
          rb[j] = k >= 0 ? a2[y][k] : n;
        } else
          rb[j] = n;
        stp[j] += d + 1;
        fix2(j);
      }
  }
  for (i = 1; i <= n; ++i) ans += 1ll * stp[i] * n - ss[i];
  cout << ans << '\n';
  return 0;
}