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;
using cat = long long;
int main() {
  cin.sync_with_stdio(0);
  cin.tie(0);
  cout << fixed << setprecision(10);
  string S;
  cin >> S;
  int N = S.length();
  if (N == 1) {
    cout << "0\n";
    return 0;
  }
  vector<vector<int> > right_occ(N, vector<int>(26, N));
  for (int i = 0; i < 26; i++)
    for (int j = N - 1; j >= 0; j--) {
      if (S[j] == 'a' + i)
        right_occ[j][i] = j;
      else if (j < N - 1)
        right_occ[j][i] = right_occ[j + 1][i];
    }
  vector<vector<int> > left_occ(N, vector<int>(26, -1));
  for (int i = 0; i < 26; i++)
    for (int j = 0; j < N - 1; j++) {
      if (S[j] == 'a' + i)
        left_occ[j][i] = j;
      else if (j > 0)
        left_occ[j][i] = left_occ[j - 1][i];
    }
  vector<pair<int, int> > I(N);
  for (int k = 0; k < 26; k++) {
    for (int i = 0, last = 0; i < N; i++)
      if (S[i] == 'a' + k) {
        I[i].first = last;
        last = i;
      }
    for (int i = N - 1, last = N - 1; i >= 0; i--)
      if (S[i] == 'a' + k) {
        I[i].second = last;
        last = i;
      }
  }
  vector<vector<int> > RMQ_I_right(20, vector<int>(N, -1));
  vector<vector<int> > RMQ_id_right(20, vector<int>(N, -1));
  for (int i = 0; i < N; i++) {
    RMQ_I_right[0][i] = I[i].second;
    RMQ_id_right[0][i] = i;
  }
  for (int k = 1; k < 20; k++)
    for (int i = 0; i <= N - (1 << k); i++) {
      RMQ_I_right[k][i] =
          max(RMQ_I_right[k - 1][i], RMQ_I_right[k - 1][i + (1 << (k - 1))]);
      if (RMQ_I_right[k][i] == RMQ_I_right[k - 1][i])
        RMQ_id_right[k][i] = RMQ_id_right[k - 1][i];
      else
        RMQ_id_right[k][i] = RMQ_id_right[k - 1][i + (1 << (k - 1))];
    }
  vector<int> next_right(N);
  for (int i = 0; i < N; i++) {
    next_right[i] = i;
    int d = I[i].second - i, cur = i + 1;
    for (int k = 0; k < 20; k++)
      if ((d >> k) & 1) {
        if (RMQ_I_right[k][cur] >= I[next_right[i]].second)
          next_right[i] = RMQ_id_right[k][cur];
        cur += 1 << k;
      }
  }
  vector<vector<int> > RMQ_I_left(20, vector<int>(N, N));
  vector<vector<int> > RMQ_id_left(20, vector<int>(N, N));
  for (int i = 0; i < N; i++) {
    RMQ_I_left[0][i] = I[i].first;
    RMQ_id_left[0][i] = i;
  }
  for (int k = 1; k < 20; k++)
    for (int i = (1 << k) - 1; i < N; i++) {
      RMQ_I_left[k][i] =
          min(RMQ_I_left[k - 1][i], RMQ_I_left[k - 1][i - (1 << (k - 1))]);
      if (RMQ_I_left[k][i] == RMQ_I_left[k - 1][i])
        RMQ_id_left[k][i] = RMQ_id_left[k - 1][i];
      else
        RMQ_id_left[k][i] = RMQ_id_left[k - 1][i - (1 << (k - 1))];
    }
  vector<int> next_left(N);
  for (int i = 0; i < N; i++) {
    next_left[i] = i;
    int d = i - I[i].first, cur = i - 1;
    for (int k = 0; k < 20; k++)
      if ((d >> k) & 1) {
        if (RMQ_I_left[k][cur] <= I[next_left[i]].first)
          next_left[i] = RMQ_id_left[k][cur];
        cur -= 1 << k;
      }
  }
  vector<vector<int> > RMQ_next_right(20, vector<int>(N));
  vector<vector<cat> > RMQ_sum_right(20, vector<cat>(N));
  for (int i = 0; i < N; i++) {
    RMQ_next_right[0][i] = next_right[i];
    RMQ_sum_right[0][i] = I[next_right[i]].second - I[i].second;
  }
  for (int k = 1; k < 20; k++)
    for (int i = 0; i < N; i++) {
      RMQ_next_right[k][i] = RMQ_next_right[k - 1][RMQ_next_right[k - 1][i]];
      RMQ_sum_right[k][i] =
          RMQ_sum_right[k - 1][i] +
          RMQ_sum_right[k - 1][RMQ_next_right[k - 1][i]] +
          (1LL << (k - 1)) * (I[RMQ_next_right[k][i]].second -
                              I[RMQ_next_right[k - 1][i]].second);
    }
  vector<vector<int> > RMQ_next_left(20, vector<int>(N));
  vector<vector<cat> > RMQ_sum_left(20, vector<cat>(N));
  for (int i = 0; i < N; i++) {
    RMQ_next_left[0][i] = next_left[i];
    RMQ_sum_left[0][i] = I[i].first - I[next_left[i]].first;
  }
  for (int k = 1; k < 20; k++)
    for (int i = 0; i < N; i++) {
      RMQ_next_left[k][i] = RMQ_next_left[k - 1][RMQ_next_left[k - 1][i]];
      RMQ_sum_left[k][i] =
          RMQ_sum_left[k - 1][i] +
          RMQ_sum_left[k - 1][RMQ_next_left[k - 1][i]] +
          (1LL << (k - 1)) *
              (I[RMQ_next_left[k - 1][i]].first - I[RMQ_next_left[k][i]].first);
    }
  cat ans = 0;
  for (int i = 0; i < N; i++) {
    cat sum = I[i].second - I[i].first, dist = 1;
    int left_cur = i, right_cur = i;
    while (I[left_cur].first > 0 || I[right_cur].second < N - 1) {
      int L = -1, R = N;
      for (int j = 0; j < 26; j++)
        if (right_occ[left_cur][j] > right_cur) {
          L = max(L, left_occ[i][j]);
          R = min(R, right_occ[i][j]);
        }
      L++, R--;
      for (int k = 19; k >= 0; k--) {
        int right_nxt = RMQ_next_right[k][right_cur];
        int left_nxt = RMQ_next_left[k][left_cur];
        if (I[left_nxt].first < L || I[right_nxt].second > R) continue;
        sum += dist * (I[right_nxt].second - I[right_cur].second) +
               RMQ_sum_right[k][right_cur];
        sum += dist * (I[left_cur].first - I[left_nxt].first) +
               RMQ_sum_left[k][left_cur];
        left_cur = left_nxt, right_cur = right_nxt;
        dist += 1 << k;
        if (I[left_cur].first == 0 && I[right_cur].second == N - 1) break;
      }
      pair<int, int> I_cur = {I[left_cur].first, I[right_cur].second};
      pair<int, int> I_nxt = I_cur;
      int left_nxt = left_cur, right_nxt = right_cur;
      for (int k = 19, cur = I_cur.first; k >= 0; k--) {
        if (cur + (1 << k) > I_cur.second + 1) continue;
        if (RMQ_I_right[k][cur] >= I_nxt.second) {
          I_nxt.second = RMQ_I_right[k][cur];
          right_nxt = RMQ_id_right[k][cur];
        }
        cur += 1 << k;
      }
      for (int k = 19, cur = I_cur.second; k >= 0; k--) {
        if (cur - (1 << k) < I_cur.first - 1) continue;
        if (RMQ_I_left[k][cur] <= I_nxt.first) {
          I_nxt.first = RMQ_I_left[k][cur];
          left_nxt = RMQ_id_left[k][cur];
        }
        cur -= 1 << k;
      }
      dist++;
      sum += dist * (I_nxt.second - I_cur.second + I_cur.first - I_nxt.first);
      left_cur = left_nxt, right_cur = right_nxt;
      I_cur = I_nxt;
    }
    ans += sum;
  }
  cout << ans << "\n";
  return 0;
}