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 <typename T>
struct outputer;
struct outputable {};
template <typename T>
inline auto sqr(T x) -> decltype(x * x) {
  return x * x;
}
template <typename T1, typename T2>
inline bool umx(T1 &a, T2 b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <typename T1, typename T2>
inline bool umn(T1 &a, T2 b) {
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}
const int N = 100000;
const int C = 26;
struct Input {
  string s;
  bool read() { return !!getline(cin, s) && ((int)(s).size()); }
  void init(const Input &input) { *this = input; }
};
struct Data : Input {
  int64_t ans;
  void write() { cout << ans << endl; }
};
namespace Main {
const int L = 17;
struct Solution : Data {
  vector<int> pos[C];
  int l[N], r[N];
  int cl[N], cr[N];
  int lm[N + 1], rm[N + 1];
  int mxr[N + 1];
  int lk[L][N + 1], rk[L][N + 1];
  int64_t sl[L][N + 1], sr[L][N + 1];
  int cnt[C];
  void solve() {
    ;
    ;
    for (int i = int(0); i < int(((int)(s).size())); ++i) {
      pos[s[i] - 'a'].emplace_back(i);
    }
    for (int c = int(0); c < int(C); ++c) {
      for (int i = int(0); i < int(((int)(pos[c]).size())); ++i) {
        l[pos[c][i]] = (i == 0) ? 0 : pos[c][i - 1];
        r[pos[c][i]] = (i == ((int)(pos[c]).size()) - 1) ? ((int)(s).size())
                                                         : pos[c][i + 1] + 1;
      }
    };
    ;
    for (int i = int(0); i < int(((int)(s).size())); ++i) {
      cl[i] = i;
      cr[i] = i + 1;
    }
    for (int m = int(1); m < int(C + 1); ++m) {
      ;
      ;
      ;
      ;
      {
        memset(cnt, 0, sizeof cnt);
        int k = 0;
        int rb = 0;
        multiset<int> ls, rs;
        rm[0] = 0;
        lm[((int)(s).size())] = ((int)(s).size());
        mxr[((int)(s).size())] = ((int)(s).size());
        for (int lb = int(0); lb < int(((int)(s).size())); ++lb) {
          while (rb < ((int)(s).size())) {
            int &x = cnt[s[rb] - 'a'];
            if (k + !x > m) {
              break;
            }
            ls.insert(l[rb]);
            rs.insert(r[rb]);
            k += !x;
            ++x;
            ++rb;
            rm[rb] = *rs.rbegin();
          }
          mxr[lb] = rb;
          lm[lb] = *ls.begin();
          int &x = cnt[s[lb] - 'a'];
          --x;
          k -= !x;
          ls.erase(ls.find(l[lb]));
          rs.erase(rs.find(r[lb]));
        }
      };
      ;
      ;
      for (int i = int(0); i < int(((int)(s).size()) + 1); ++i) {
        lk[0][i] = lm[i];
        rk[0][i] = rm[i];
        sl[0][i] = i;
        sr[0][i] = ((int)(s).size()) - i;
      }
      for (int t = int(0); t < int(L - 1); ++t) {
        for (int i = int(0); i < int(((int)(s).size()) + 1); ++i) {
          lk[t + 1][i] = lk[t][lk[t][i]];
          rk[t + 1][i] = rk[t][rk[t][i]];
          sl[t + 1][i] = sl[t][i] + sl[t][lk[t][i]];
          sr[t + 1][i] = sr[t][i] + sr[t][rk[t][i]];
        }
      }
      for (int t = int(0); t < int(L); ++t) {
        ;
        ;
        ;
        ;
        ;
        ;
      }
      for (int i = int(0); i < int(((int)(s).size())); ++i) {
        for (int t = int(L) - 1; t >= int(0); --t) {
          int nl = lk[t][cl[i]];
          int nr = rk[t][cr[i]];
          if (nr <= mxr[nl]) {
            ans += sl[t][cl[i]];
            ans += sr[t][cr[i]];
            cl[i] = nl;
            cr[i] = nr;
          }
        }
        if (cr[i] <= mxr[cl[i]]) {
          ans += cl[i];
          ans += ((int)(s).size()) - cr[i];
          cl[i] = lm[cl[i]];
          cr[i] = rm[cr[i]];
        }
      }
    }
  }
  void clear() { *this = Solution(); }
};
}  // namespace Main
Main::Solution sol;
int main() {
  cout.setf(ios::showpoint | ios::fixed);
  cout.precision(20);
  sol.read();
  sol.solve();
  sol.write();
  return 0;
}