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;
int read() {
  int x = 0;
  bool flg = false;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') flg = true;
  for (; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48);
  return flg ? -x : x;
}
const int INF = 1e6;
char s[100010];
int n;
int L[100010], R[100010];
long long ans;
int pre[100010][26], suf[100010][26];
int lj[17][100010], rj[17][100010];
long long lw[17][100010], rw[17][100010];
void work(int o) {
  for (int i(1), _i(n); i <= _i; i++) {
    static int c[26];
    memcpy(c, suf[i], sizeof c);
    nth_element(c, c + o - 1, c + 26);
    int mn = i;
    for (int j(0), _j(o - 1); j <= _j; j++) {
      const int &p = c[j];
      if (p == n + 1) continue;
      mn = min(mn, pre[p - 1][s[p] - 'a']);
    }
    mn = max(mn, 1);
    lj[0][i] = mn, lw[0][i] = mn;
    for (int j(1), _j(16); j <= _j; j++)
      lj[j][i] = lj[j - 1][lj[j - 1][i]],
      lw[j][i] = lw[j - 1][i] + lw[j - 1][lj[j - 1][i]];
  }
  for (int i(n), _i(1); i >= _i; i--) {
    static int c[26];
    memcpy(c, pre[i], sizeof c);
    nth_element(c, c + o - 1, c + 26, greater<int>());
    int mx = i;
    for (int j(0), _j(o - 1); j <= _j; j++) {
      const int &p = c[j];
      if (p == 0) continue;
      mx = max(mx, suf[p + 1][s[p] - 'a']);
    }
    mx = min(mx, n);
    rj[0][i] = mx, rw[0][i] = mx;
    for (int j(1), _j(16); j <= _j; j++)
      rj[j][i] = rj[j - 1][rj[j - 1][i]],
      rw[j][i] = rw[j - 1][i] + rw[j - 1][rj[j - 1][i]];
  }
  static int lim[100010], c[26], d;
  memset(c, 0, sizeof c);
  d = 0;
  for (int i = n, l = n + 1, r = n; i; --i) {
    if (!(c[s[--l] - 'a']++)) ++d;
    while (d > o) d -= !--c[s[r--] - 'a'];
    lim[i] = r;
  }
  const auto check = [&](int l, int r) { return r <= lim[l]; };
  for (int i(1), _i(n); i <= _i; i++) {
    int &l = L[i], &r = R[i];
    if (!check(l, r)) continue;
    for (int j(16), _j(0); j >= _j; j--) {
      if (check(lj[j][l], rj[j][r]))
        ans += 1LL * (n - 1) * (1 << j) - rw[j][r] + lw[j][l], l = lj[j][l],
                                                               r = rj[j][r];
    }
    ans += n - 1 - rw[0][r] + lw[0][l];
    l = lj[0][l], r = rj[0][r];
  }
}
void solve() {
  scanf("%s", s + 1);
  n = strlen(s + 1);
  for (int i(1), _i(n); i <= _i; i++) {
    memcpy(pre[i], pre[i - 1], 26 << 2);
    pre[i][s[i] - 'a'] = i;
  }
  fill(suf[n + 1], suf[n + 1] + 26, n + 1);
  for (int i(n), _i(1); i >= _i; i--) {
    memcpy(suf[i], suf[i + 1], 26 << 2);
    suf[i][s[i] - 'a'] = i;
  }
  for (int i(1), _i(n); i <= _i; i++) L[i] = R[i] = i, ans += n - 1;
  for (int t(1), _t(26); t <= _t; t++) work(t);
  printf("%lld\n", ans);
}
int main() {
  for (int T = 1; T--;) solve();
  return 0;
}