#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int suf[N][27], pre[N][27];
int isuf[N][27], ipre[N][27];
int stl[20][N], str[20][N];
long long Sl[20][N], Sr[20][N];
int lvl[N], L[N], R[N], T[N];
int n, le[N], ri[N], lg[N];
char s[N];
long long ans;
int main() {
  scanf("%s", s + 1);
  n = strlen(s + 1);
  for (int i = (int)(1); i <= (int)(n); i++) s[i] -= 'a';
  for (int i = (int)(0); i <= (int)(25); i++) {
    suf[n][i] = suf[n + 1][i] = n + 1;
    ipre[0][i] = ipre[1][i] = i;
    isuf[n][i] = isuf[n + 1][i] = i;
  }
  for (int i = (int)(1); i <= (int)(n); i++) {
    for (int j = (int)(0); j <= (int)(25); j++) pre[i + 1][j] = pre[i][j];
    pre[i + 1][s[i]] = i;
    ipre[i + 1][0] = s[i];
    int tmp = 1;
    for (int j = (int)(0); j <= (int)(25); j++)
      if (ipre[i][j] != s[i]) ipre[i + 1][tmp++] = ipre[i][j];
  }
  for (int i = (int)(n); i >= (int)(1); i--) {
    for (int j = (int)(0); j <= (int)(25); j++) suf[i - 1][j] = suf[i][j];
    suf[i - 1][s[i]] = i;
    isuf[i - 1][0] = s[i];
    int tmp = 1;
    for (int j = (int)(0); j <= (int)(25); j++)
      if (isuf[i][j] != s[i]) isuf[i - 1][tmp++] = isuf[i][j];
  }
  for (int i = (int)(1); i <= (int)(n); i++) {
    L[i] = le[i] = max(1, pre[i][s[i]]);
    R[i] = ri[i] = min(n, suf[i][s[i]]);
    stl[0][i] = n;
    str[0][i] = 1;
    lvl[i] = 0;
    T[i] = 1;
    ans += n - 1;
    for (int j = (int)(0); j <= (int)(25); j++)
      lvl[i] += (suf[L[i] - 1][j] <= R[i]);
  }
  ri[0] = n;
  le[n + 1] = 1;
  for (int i = (int)(2); i <= (int)(n); i++) lg[i] = lg[i / 2] + 1;
  cerr << clock() << endl;
  for (int i = (int)(1); i <= (int)(26); i++) {
    for (int j = (int)(1); j <= (int)(n); j++) {
      Sl[0][j] = j - 1;
      Sr[0][j] = n - j;
      stl[0][j] = min(stl[0][j], le[suf[j - 1][isuf[j - 1][i - 1]]]);
      str[0][j] = max(str[0][j], ri[pre[j + 1][ipre[j + 1][i - 1]]]);
    }
    for (int j = (int)(1); j <= (int)(lg[n / i]); j++)
      for (int k = (int)(1); k <= (int)(n); k++) {
        stl[j][k] = stl[j - 1][stl[j - 1][k]];
        str[j][k] = str[j - 1][str[j - 1][k]];
        Sl[j][k] = Sl[j - 1][k] + Sl[j - 1][stl[j - 1][k]];
        Sr[j][k] = Sr[j - 1][k] + Sr[j - 1][str[j - 1][k]];
      }
    for (int j = (int)(1); j <= (int)(n); j++)
      if (lvl[j] == i) {
        int pl = L[j], pr = R[j];
        int liml = (i == 26 ? 0 : pre[pr + 1][ipre[pr + 1][i]]);
        int limr = (i == 26 ? n + 1 : suf[pl - 1][isuf[pl - 1][i]]);
        for (int k = (int)(lg[n / i]); k >= (int)(0); k--)
          if (stl[k][pl] > liml && str[k][pr] < limr) {
            ans += Sl[k][pl] + Sr[k][pr];
            pl = stl[k][pl];
            pr = str[k][pr];
          }
        ans += pl - 1 + n - pr;
        L[j] = pl = stl[0][pl];
        R[j] = pr = str[0][pr];
        lvl[j] = 0;
        for (int k = (int)(0); k <= (int)(25); k++)
          lvl[j] += (suf[pl - 1][k] <= pr);
      }
  }
  printf("%lld\n", ans);
}

### Prompt

Please formulate a cpp solution to the following 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.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int suf[N][27], pre[N][27];
int isuf[N][27], ipre[N][27];
int stl[20][N], str[20][N];
long long Sl[20][N], Sr[20][N];
int lvl[N], L[N], R[N], T[N];
int n, le[N], ri[N], lg[N];
char s[N];
long long ans;
int main() {
  scanf("%s", s + 1);
  n = strlen(s + 1);
  for (int i = (int)(1); i <= (int)(n); i++) s[i] -= 'a';
  for (int i = (int)(0); i <= (int)(25); i++) {
    suf[n][i] = suf[n + 1][i] = n + 1;
    ipre[0][i] = ipre[1][i] = i;
    isuf[n][i] = isuf[n + 1][i] = i;
  }
  for (int i = (int)(1); i <= (int)(n); i++) {
    for (int j = (int)(0); j <= (int)(25); j++) pre[i + 1][j] = pre[i][j];
    pre[i + 1][s[i]] = i;
    ipre[i + 1][0] = s[i];
    int tmp = 1;
    for (int j = (int)(0); j <= (int)(25); j++)
      if (ipre[i][j] != s[i]) ipre[i + 1][tmp++] = ipre[i][j];
  }
  for (int i = (int)(n); i >= (int)(1); i--) {
    for (int j = (int)(0); j <= (int)(25); j++) suf[i - 1][j] = suf[i][j];
    suf[i - 1][s[i]] = i;
    isuf[i - 1][0] = s[i];
    int tmp = 1;
    for (int j = (int)(0); j <= (int)(25); j++)
      if (isuf[i][j] != s[i]) isuf[i - 1][tmp++] = isuf[i][j];
  }
  for (int i = (int)(1); i <= (int)(n); i++) {
    L[i] = le[i] = max(1, pre[i][s[i]]);
    R[i] = ri[i] = min(n, suf[i][s[i]]);
    stl[0][i] = n;
    str[0][i] = 1;
    lvl[i] = 0;
    T[i] = 1;
    ans += n - 1;
    for (int j = (int)(0); j <= (int)(25); j++)
      lvl[i] += (suf[L[i] - 1][j] <= R[i]);
  }
  ri[0] = n;
  le[n + 1] = 1;
  for (int i = (int)(2); i <= (int)(n); i++) lg[i] = lg[i / 2] + 1;
  cerr << clock() << endl;
  for (int i = (int)(1); i <= (int)(26); i++) {
    for (int j = (int)(1); j <= (int)(n); j++) {
      Sl[0][j] = j - 1;
      Sr[0][j] = n - j;
      stl[0][j] = min(stl[0][j], le[suf[j - 1][isuf[j - 1][i - 1]]]);
      str[0][j] = max(str[0][j], ri[pre[j + 1][ipre[j + 1][i - 1]]]);
    }
    for (int j = (int)(1); j <= (int)(lg[n / i]); j++)
      for (int k = (int)(1); k <= (int)(n); k++) {
        stl[j][k] = stl[j - 1][stl[j - 1][k]];
        str[j][k] = str[j - 1][str[j - 1][k]];
        Sl[j][k] = Sl[j - 1][k] + Sl[j - 1][stl[j - 1][k]];
        Sr[j][k] = Sr[j - 1][k] + Sr[j - 1][str[j - 1][k]];
      }
    for (int j = (int)(1); j <= (int)(n); j++)
      if (lvl[j] == i) {
        int pl = L[j], pr = R[j];
        int liml = (i == 26 ? 0 : pre[pr + 1][ipre[pr + 1][i]]);
        int limr = (i == 26 ? n + 1 : suf[pl - 1][isuf[pl - 1][i]]);
        for (int k = (int)(lg[n / i]); k >= (int)(0); k--)
          if (stl[k][pl] > liml && str[k][pr] < limr) {
            ans += Sl[k][pl] + Sr[k][pr];
            pl = stl[k][pl];
            pr = str[k][pr];
          }
        ans += pl - 1 + n - pr;
        L[j] = pl = stl[0][pl];
        R[j] = pr = str[0][pr];
        lvl[j] = 0;
        for (int k = (int)(0); k <= (int)(25); k++)
          lvl[j] += (suf[pl - 1][k] <= pr);
      }
  }
  printf("%lld\n", ans);
}

```