#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
inline int read() {
  char c = getchar();
  int out = 0;
  while (!(c >= '0' && c <= '9')) c = getchar();
  while (c >= '0' && c <= '9') out = out * 10 + c - '0', c = getchar();
  return out;
}
inline int add(int a, int b) {
  if ((a += b) >= mod) a -= mod;
  return a;
}
inline int dec(int a, int b) {
  if ((a -= b) < 0) a += mod;
  return a;
}
inline int mult(int a, int b) {
  long long t = 1ll * a * b;
  if (t >= mod) t %= mod;
  return t;
}
inline int power(int a, int b) {
  int out = 1;
  while (b) {
    if (b & 1) out = mult(out, a);
    a = mult(a, a);
    b >>= 1;
  }
  return out;
}
char s[100010];
int a[100010], n, fl[18][100010], fr[18][100010], L[100010], ext[100010],
    R[100010], cur[26], cnt[26], curl[100010], curr[100010];
long long ans, suml[18][100010], sumr[18][100010];
inline void jump(int p, int x) {
  ans += sumr[x][curr[p]] + suml[x][curl[p]];
  curr[p] = fr[x][curr[p]];
  curl[p] = fl[x][curl[p]];
}
int main() {
  scanf("%s", s + 1);
  n = strlen(s + 1);
  for (int i = 1; i <= n; i++) a[i] = s[i] - 'a', curl[i] = curr[i] = i;
  fill(cur, cur + 26, 1);
  for (int i = 1; i <= n; i++) L[i] = cur[a[i]], cur[a[i]] = i;
  fill(cur, cur + 26, n);
  for (int i = n; i >= 1; i--) R[i] = cur[a[i]], cur[a[i]] = i;
  for (int t = 1; t <= 26; t++) {
    multiset<int> sl, sr;
    int cur = 0;
    for (int l = 1, r = 1; l <= n; l++) {
      while (r <= n && cur + (cnt[a[r]] == 0) <= t) {
        sl.insert(L[r]);
        sr.insert(R[r]);
        cur += (cnt[a[r]] == 0);
        fr[0][r] = *--sr.end();
        cnt[a[r]]++;
        r++;
      }
      fl[0][l] = *sl.begin();
      cnt[a[l]]--;
      cur -= !cnt[a[l]];
      suml[0][l] = l - 1;
      sumr[0][l] = n - l;
      ext[l] = r;
      sl.erase(sl.find(L[l]));
      sr.erase(sr.find(R[l]));
    }
    for (int j = 1; j < 18; j++) {
      for (int i = 1; i <= n; i++) {
        fl[j][i] = fl[j - 1][fl[j - 1][i]];
        fr[j][i] = fr[j - 1][fr[j - 1][i]];
        suml[j][i] = suml[j - 1][i] + suml[j - 1][fl[j - 1][i]];
        sumr[j][i] = sumr[j - 1][i] + sumr[j - 1][fr[j - 1][i]];
      }
    }
    for (int i = 1; i <= n; i++) {
      for (int j = 17; j >= 0; j--) {
        if (fr[j][curr[i]] < ext[fl[j][curl[i]]]) jump(i, j);
      }
      if (curr[i] < ext[curl[i]]) jump(i, 0);
    }
  }
  printf("%lld\n", ans);
  return 0;
}

### Prompt

Your task is to create 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 mod = 998244353;
inline int read() {
  char c = getchar();
  int out = 0;
  while (!(c >= '0' && c <= '9')) c = getchar();
  while (c >= '0' && c <= '9') out = out * 10 + c - '0', c = getchar();
  return out;
}
inline int add(int a, int b) {
  if ((a += b) >= mod) a -= mod;
  return a;
}
inline int dec(int a, int b) {
  if ((a -= b) < 0) a += mod;
  return a;
}
inline int mult(int a, int b) {
  long long t = 1ll * a * b;
  if (t >= mod) t %= mod;
  return t;
}
inline int power(int a, int b) {
  int out = 1;
  while (b) {
    if (b & 1) out = mult(out, a);
    a = mult(a, a);
    b >>= 1;
  }
  return out;
}
char s[100010];
int a[100010], n, fl[18][100010], fr[18][100010], L[100010], ext[100010],
    R[100010], cur[26], cnt[26], curl[100010], curr[100010];
long long ans, suml[18][100010], sumr[18][100010];
inline void jump(int p, int x) {
  ans += sumr[x][curr[p]] + suml[x][curl[p]];
  curr[p] = fr[x][curr[p]];
  curl[p] = fl[x][curl[p]];
}
int main() {
  scanf("%s", s + 1);
  n = strlen(s + 1);
  for (int i = 1; i <= n; i++) a[i] = s[i] - 'a', curl[i] = curr[i] = i;
  fill(cur, cur + 26, 1);
  for (int i = 1; i <= n; i++) L[i] = cur[a[i]], cur[a[i]] = i;
  fill(cur, cur + 26, n);
  for (int i = n; i >= 1; i--) R[i] = cur[a[i]], cur[a[i]] = i;
  for (int t = 1; t <= 26; t++) {
    multiset<int> sl, sr;
    int cur = 0;
    for (int l = 1, r = 1; l <= n; l++) {
      while (r <= n && cur + (cnt[a[r]] == 0) <= t) {
        sl.insert(L[r]);
        sr.insert(R[r]);
        cur += (cnt[a[r]] == 0);
        fr[0][r] = *--sr.end();
        cnt[a[r]]++;
        r++;
      }
      fl[0][l] = *sl.begin();
      cnt[a[l]]--;
      cur -= !cnt[a[l]];
      suml[0][l] = l - 1;
      sumr[0][l] = n - l;
      ext[l] = r;
      sl.erase(sl.find(L[l]));
      sr.erase(sr.find(R[l]));
    }
    for (int j = 1; j < 18; j++) {
      for (int i = 1; i <= n; i++) {
        fl[j][i] = fl[j - 1][fl[j - 1][i]];
        fr[j][i] = fr[j - 1][fr[j - 1][i]];
        suml[j][i] = suml[j - 1][i] + suml[j - 1][fl[j - 1][i]];
        sumr[j][i] = sumr[j - 1][i] + sumr[j - 1][fr[j - 1][i]];
      }
    }
    for (int i = 1; i <= n; i++) {
      for (int j = 17; j >= 0; j--) {
        if (fr[j][curr[i]] < ext[fl[j][curl[i]]]) jump(i, j);
      }
      if (curr[i] < ext[curl[i]]) jump(i, 0);
    }
  }
  printf("%lld\n", ans);
  return 0;
}

```