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>
#pragma GCC optimize("Ofast,no-stack-protector")
using namespace std;
string s;
const int maxn = (int)1e5 + 1;
const int maxlog = 19;
struct vt {
  int w[26];
  vector<int> lnk[26];
  vector<int> rlnk[26];
  string s;
  vt() {}
  vt(string s) : s(s) {}
  int get_cnt(int l, int r) {
    int ans = 0;
    for (int i = 0; i < 26; i++) {
      if (lnk[i][r] >= l || i == s[r] - 'a') {
        ans++;
      }
    }
    return ans - 1;
  }
  vector<long long> sum[1][26];
  vector<pair<int, int> > tab[1][26];
  void build() {
    memset(w, -1, sizeof w);
    for (int i = 0; i < 26; i++) {
      lnk[i].resize(s.size());
      rlnk[i].resize(s.size());
      for (int j = 0; j < 1; j++) {
        sum[j][i].resize(s.size());
        tab[j][i].resize(s.size());
      }
    }
    for (int i = 0; i < (int)s.size(); i++) {
      for (int j = 0; j < 26; j++) {
        lnk[j][i] = w[j];
      }
      w[s[i] - 'a'] = i;
    }
    for (int j = 0; j < 26; j++) {
      w[j] = (int)s.size() - 1;
    }
    for (int i = (int)s.size() - 1; i >= 0; i--) {
      for (int j = 0; j < 26; j++) {
        rlnk[j][i] = w[j];
      }
      w[s[i] - 'a'] = i;
    }
    for (int i = 0; i < (int)s.size(); i++) {
      vector<int> g;
      for (int j = 0; j < 26; j++) {
        if (j != s[i] - 'a') {
          g.push_back(lnk[j][i]);
        } else {
          g.push_back(i);
        }
      }
      sort(g.rbegin(), g.rend());
      int rm = i;
      for (int j = 0; j < (int)g.size(); j++) {
        if (g[j] == -1) {
          tab[0][j][i] = tab[0][j - 1][i];
          sum[0][j][i] = sum[0][j - 1][i];
          continue;
        }
        rm = max(rm, rlnk[s[g[j]] - 'a'][g[j]]);
        int lm = g[j];
        int cnt = get_cnt(lm, rm);
        tab[0][j][i] = make_pair(cnt, rm);
        sum[0][j][i] = rm;
      }
    }
  }
  vector<long long> sums[maxlog];
  vector<int> tot[maxlog];
  vector<int> tabs[maxlog];
  void build(int k) {
    for (int i = 0; i < maxlog; i++) {
      sums[i].assign(s.size(), 0);
      tabs[i].assign(s.size(), -1);
      tot[i].assign(s.size(), 0);
    }
    for (int i = 0; i < (int)s.size(); i++) {
      if (tab[0][k][i].first == k) {
        sums[0][i] = tab[0][k][i].second;
        tabs[0][i] = tab[0][k][i].second;
        tot[0][i] = 1;
      } else {
        sums[0][i] = 0;
        tabs[0][i] = i;
        tot[0][i] = 0;
      }
    }
    for (int it = 1; it < maxlog; it++) {
      for (int i = 0; i < (int)s.size(); i++) {
        tabs[it][i] = tabs[it - 1][tabs[it - 1][i]];
        sums[it][i] = sums[it - 1][i] + sums[it - 1][tabs[it - 1][i]];
        tot[it][i] = tot[it - 1][i] + tot[it - 1][tabs[it - 1][i]];
      }
    }
  }
};
long long stup(int pos) {
  int lm = pos;
  int rm = pos;
  int n = (int)s.size();
  long long ans = 0;
  while (rm - lm + 1 != n) {
    ans += n - 1 - (rm - lm);
    int mask = 0;
    for (int i = lm; i <= rm; i++) {
      mask |= (1 << (s[i] - 'a'));
    }
    int l = lm;
    while (lm > 0 && mask != 0) {
      lm--;
      int c = s[lm] - 'a';
      if ((mask >> c) & 1) {
        mask ^= (1 << c);
      }
    }
    mask = 0;
    for (int i = l; i <= rm; i++) {
      mask |= (1 << (s[i] - 'a'));
    }
    while (rm < n - 1 && mask != 0) {
      rm++;
      int c = s[rm] - 'a';
      if ((mask >> c) & 1) {
        mask ^= (1 << c);
      }
    }
  }
  return ans;
}
int main() {
  cin >> s;
  for (int i = 0; i < (int)1e4; i++) {
  }
  vt dpr = vt(s);
  dpr.build();
  reverse(s.begin(), s.end());
  vt dpl = vt(s);
  dpl.build();
  reverse(s.begin(), s.end());
  long long ans = 0;
  long long pre = 0;
  int n = (int)s.size();
  vector<pair<int, int> > cur;
  for (int i = 0; i < (int)s.size(); i++) {
    cur.push_back(make_pair(n - 1 - i, i));
    ans += n - 1;
  }
  for (int j = 0; j < 26; j++) {
    dpr.build(j);
    dpl.build(j);
    for (int i = 0; i < (int)s.size(); i++) {
      int lm = cur[i].first;
      int rm = cur[i].second;
      int cnt = dpr.get_cnt(n - 1 - lm, rm);
      if (cnt == j) {
        for (int it = maxlog - 1; it >= 0; it--) {
          if (dpr.tot[it][rm] == (1 << it) && dpl.tot[it][lm] == (1 << it)) {
            ans -= dpr.sums[it][rm];
            rm = dpr.tabs[it][rm];
            ans -= dpl.sums[it][lm];
            ans += 2ll * (n - 1) * (1 << it);
            lm = dpl.tabs[it][lm];
          }
        }
        rm = dpr.tab[0][cnt][rm].second;
        lm = dpl.tab[0][cnt][lm].second;
        ans -= rm + lm;
        ans += 2 * (n - 1);
        cur[i].first = lm;
        cur[i].second = rm;
      }
    }
  }
  cout << ans << endl;
}