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;
template <class T>
inline void rd(T &x) {
  x = 0;
  char c = getchar();
  int f = 1;
  while (!isdigit(c)) {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (isdigit(c)) x = x * 10 - '0' + c, c = getchar();
  x *= f;
}
const int N = 1e5 + 10;
char T[N];
int S[N];
int n, Lg[N], bit[1 << 17];
int bitcount(int x) {
  if (!x) return 0;
  return bit[x & ((1 << 17) - 1)] + bitcount(x >> 17);
}
namespace ST {
int st[18][N];
void predo() {
  for (int i = 1; i < (1 << 17); ++i) bit[i] = bit[i & (i - 1)] + 1;
  for (int i = 2; i <= n; ++i) Lg[i] = Lg[i >> 1] + 1;
  for (int i = 1; i <= n; ++i) st[0][i] = 1 << S[i];
  for (int j = 1; j <= 17; ++j)
    for (int i = 1; i + (1 << j) - 1 <= n; ++i)
      st[j][i] = st[j - 1][i] | st[j - 1][i + (1 << j - 1)];
}
int query(int l, int r) {
  int L = Lg[r - l + 1];
  return bitcount(st[L][l] | st[L][r - (1 << L) + 1]);
}
}  // namespace ST
int lst[N][26], nxt[N][26], L[N], R[N];
int fL[19][N], fR[19][N], pl[N], pr[N];
long long gL[19][N], gR[19][N];
vector<char> ss;
int main() {
  scanf("%s", T + 1);
  n = strlen(T + 1);
  for (int i = 1; i <= n; ++i) ss.push_back(T[i]);
  sort(ss.begin(), ss.end());
  ss.resize(unique(ss.begin(), ss.end()) - ss.begin());
  for (int i = 1; i <= n; ++i)
    S[i] = lower_bound(ss.begin(), ss.end(), T[i]) - ss.begin();
  ST::predo();
  for (int i = 0; i < ss.size(); ++i) lst[1][i] = 1, nxt[n][i] = n;
  for (int i = 2; i <= n; ++i) {
    memcpy(lst[i], lst[i - 1], sizeof(lst[i]));
    lst[i][S[i]] = i;
  }
  for (int i = n - 1; i >= 1; --i) {
    memcpy(nxt[i], nxt[i + 1], sizeof(nxt[i]));
    nxt[i][S[i]] = i;
  }
  for (int i = 1; i <= n; ++i) {
    L[i] = i == 1 ? 1 : lst[i - 1][S[i]];
    R[i] = i == n ? n : nxt[i + 1][S[i]];
    pl[i] = pr[i] = i;
    fL[0][i] = n + 1, fR[0][i] = 0;
  }
  for (int i = 1; i <= n; ++i) {
    sort(lst[i], lst[i] + ss.size(), greater<int>());
    sort(nxt[i], nxt[i] + ss.size());
  }
  long long ans = 0;
  for (int t = 0; t < ss.size(); ++t) {
    for (int i = 1; i <= n; ++i) {
      gL[0][i] = (fL[0][i] = min(fL[0][i], L[nxt[i][t]]));
      gR[0][i] = (fR[0][i] = max(fR[0][i], R[lst[i][t]]));
    }
    for (int j = 1; j <= 18; ++j)
      for (int i = 1; i <= n; ++i) {
        fL[j][i] = fL[j - 1][fL[j - 1][i]],
        gL[j][i] = gL[j - 1][i] + gL[j - 1][fL[j - 1][i]];
        fR[j][i] = fR[j - 1][fR[j - 1][i]],
        gR[j][i] = gR[j - 1][i] + gR[j - 1][fR[j - 1][i]];
      }
    for (int i = 1; i <= n; ++i) {
      if (ST::query(pl[i], pr[i]) > t + 1) continue;
      ans += n - 1 - (pr[i] - pl[i]);
      for (int j = 18; j >= 0; --j) {
        int l = fL[j][pl[i]], r = fR[j][pr[i]];
        if (ST::query(l, r) == t + 1) {
          ans += (n - 1) * (1ll << j) - (gR[j][pr[i]] - gL[j][pl[i]]);
          pl[i] = l, pr[i] = r;
        }
      }
      pl[i] = fL[0][pl[i]], pr[i] = fR[0][pr[i]];
    }
  }
  printf("%lld", ans);
  return 0;
}