#include <bits/stdc++.h>
using namespace std;
const int LOG = 17;
const int N = 100005;
const int ALPHA = 26;
string s;
int f[2][LOG][N], mask[LOG][N], n, LG[N], L[N], R[N], g[2][LOG][N],
    prv[2][ALPHA][N], nxt[2][ALPHA][N], nw[2][ALPHA][N], buffer[ALPHA];
int lft[N];
long long suma[2][LOG][N];
int I, letters[26];
void build() {
  for (int i = 0; i < ALPHA; i++) letters[i] = i;
  int k = -1;
  for (int i = 1; i < N; i++) {
    if (i == (1 << (k + 1))) k++;
    LG[i] = k;
  }
  for (int i = 0; i < n; i++) mask[0][i] = 1 << s[i];
  for (int i = 1; i < LOG; i++)
    for (int j = 0; j < n - (1 << i) + 1; j++)
      mask[i][j] = mask[i - 1][j] | mask[i - 1][j + (1 << (i - 1))];
}
int distinct(int l, int r) {
  int lenLog = LG[r - l + 1];
  return __builtin_popcount(mask[lenLog][l] |
                            mask[lenLog][r - (1 << lenLog) + 1]) -
         1;
}
bool cmp(int i1, int i2) { return abs(I - buffer[i1]) < abs(I - buffer[i2]); }
void getLast() {
  for (int i = 0; i < 2; i++) {
    for (int k = 0; k < ALPHA; k++) prv[i][k][0] = -1;
    for (int j = 0; j < n; j++) {
      prv[i][s[j]][j] = j;
      for (int k = 0; k < ALPHA; k++) {
        prv[i][k][j + 1] = prv[i][k][j];
        nxt[i ^ 1][k][j + 1] = s[j] == k ? j : nxt[i ^ 1][k][j];
      }
    }
    reverse(s.begin(), s.end());
  }
  for (int j = 0; j < ALPHA; j++) {
    for (int i = 0; i < n; i++) {
      prv[1][j][i] = n - 1 - prv[1][j][i];
    }
    reverse(prv[1][j], prv[1][j] + n);
    reverse(nxt[0][j], nxt[0][j] + n);
  }
  for (int i = 0; i < 2; i++)
    for (int j = 0; j < n; j++) {
      I = j;
      for (int k = 0; k < ALPHA; k++) buffer[k] = prv[i][k][j];
      sort(letters, letters + ALPHA, cmp);
      for (int k = 0; k < ALPHA; k++)
        nw[i ^ 1][k][j] = k == 0
                              ? nxt[i][letters[k]][j]
                              : min(nxt[i][letters[k]][j], nw[i ^ 1][k - 1][j]);
    }
  for (int j = 0; j < ALPHA; j++)
    for (int i = 0; i < n; i++) {
      nw[1][j][i] = n - 1 - nw[1][j][i];
      nxt[0][j][i] = n - 1 - nxt[0][j][i];
    }
}
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> s;
  for (auto &first : s) first -= 'a';
  n = (int)(s.size());
  build();
  getLast();
  long long ans = n * (long long)n * n;
  for (int i = 0; i < n; i++) L[i] = i, R[i] = i, lft[i] = n;
  for (int t = 0; t < ALPHA; t++) {
    for (int i = 0; i < n; i++)
      for (int j = 0; j < 2; j++) {
        g[j][0][i] = nw[j][t][i];
        suma[j][0][i] = i + j;
      }
    for (int i = 1; i < LOG; i++)
      for (int j = 0; j < n; j++)
        for (int k = 0; k < 2; k++) {
          g[k][i][j] = g[k][i - 1][g[k][i - 1][j]];
          suma[k][i][j] = suma[k][i - 1][j] + suma[k][i - 1][g[k][i - 1][j]];
        }
    for (int i = 0; i < n; i++) {
      for (int bit = 16; bit >= 0; bit--) {
        int newL = g[0][bit][L[i]], newR = g[1][bit][R[i]];
        if (distinct(newL, newR) == t && lft[i] >= (1 << bit)) {
          lft[i] -= (1 << bit);
          ans -= suma[1][bit][R[i]] - suma[0][bit][L[i]];
          L[i] = newL, R[i] = newR;
        }
      }
      if (distinct(L[i], R[i]) == t && lft[i]) {
        lft[i]--;
        ans -= suma[1][0][R[i]] - suma[0][0][L[i]];
        L[i] = g[0][0][L[i]], R[i] = g[1][0][R[i]];
      }
    }
  }
  cout << ans;
}

### Prompt

In Cpp, your task is to solve the following 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.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int LOG = 17;
const int N = 100005;
const int ALPHA = 26;
string s;
int f[2][LOG][N], mask[LOG][N], n, LG[N], L[N], R[N], g[2][LOG][N],
    prv[2][ALPHA][N], nxt[2][ALPHA][N], nw[2][ALPHA][N], buffer[ALPHA];
int lft[N];
long long suma[2][LOG][N];
int I, letters[26];
void build() {
  for (int i = 0; i < ALPHA; i++) letters[i] = i;
  int k = -1;
  for (int i = 1; i < N; i++) {
    if (i == (1 << (k + 1))) k++;
    LG[i] = k;
  }
  for (int i = 0; i < n; i++) mask[0][i] = 1 << s[i];
  for (int i = 1; i < LOG; i++)
    for (int j = 0; j < n - (1 << i) + 1; j++)
      mask[i][j] = mask[i - 1][j] | mask[i - 1][j + (1 << (i - 1))];
}
int distinct(int l, int r) {
  int lenLog = LG[r - l + 1];
  return __builtin_popcount(mask[lenLog][l] |
                            mask[lenLog][r - (1 << lenLog) + 1]) -
         1;
}
bool cmp(int i1, int i2) { return abs(I - buffer[i1]) < abs(I - buffer[i2]); }
void getLast() {
  for (int i = 0; i < 2; i++) {
    for (int k = 0; k < ALPHA; k++) prv[i][k][0] = -1;
    for (int j = 0; j < n; j++) {
      prv[i][s[j]][j] = j;
      for (int k = 0; k < ALPHA; k++) {
        prv[i][k][j + 1] = prv[i][k][j];
        nxt[i ^ 1][k][j + 1] = s[j] == k ? j : nxt[i ^ 1][k][j];
      }
    }
    reverse(s.begin(), s.end());
  }
  for (int j = 0; j < ALPHA; j++) {
    for (int i = 0; i < n; i++) {
      prv[1][j][i] = n - 1 - prv[1][j][i];
    }
    reverse(prv[1][j], prv[1][j] + n);
    reverse(nxt[0][j], nxt[0][j] + n);
  }
  for (int i = 0; i < 2; i++)
    for (int j = 0; j < n; j++) {
      I = j;
      for (int k = 0; k < ALPHA; k++) buffer[k] = prv[i][k][j];
      sort(letters, letters + ALPHA, cmp);
      for (int k = 0; k < ALPHA; k++)
        nw[i ^ 1][k][j] = k == 0
                              ? nxt[i][letters[k]][j]
                              : min(nxt[i][letters[k]][j], nw[i ^ 1][k - 1][j]);
    }
  for (int j = 0; j < ALPHA; j++)
    for (int i = 0; i < n; i++) {
      nw[1][j][i] = n - 1 - nw[1][j][i];
      nxt[0][j][i] = n - 1 - nxt[0][j][i];
    }
}
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> s;
  for (auto &first : s) first -= 'a';
  n = (int)(s.size());
  build();
  getLast();
  long long ans = n * (long long)n * n;
  for (int i = 0; i < n; i++) L[i] = i, R[i] = i, lft[i] = n;
  for (int t = 0; t < ALPHA; t++) {
    for (int i = 0; i < n; i++)
      for (int j = 0; j < 2; j++) {
        g[j][0][i] = nw[j][t][i];
        suma[j][0][i] = i + j;
      }
    for (int i = 1; i < LOG; i++)
      for (int j = 0; j < n; j++)
        for (int k = 0; k < 2; k++) {
          g[k][i][j] = g[k][i - 1][g[k][i - 1][j]];
          suma[k][i][j] = suma[k][i - 1][j] + suma[k][i - 1][g[k][i - 1][j]];
        }
    for (int i = 0; i < n; i++) {
      for (int bit = 16; bit >= 0; bit--) {
        int newL = g[0][bit][L[i]], newR = g[1][bit][R[i]];
        if (distinct(newL, newR) == t && lft[i] >= (1 << bit)) {
          lft[i] -= (1 << bit);
          ans -= suma[1][bit][R[i]] - suma[0][bit][L[i]];
          L[i] = newL, R[i] = newR;
        }
      }
      if (distinct(L[i], R[i]) == t && lft[i]) {
        lft[i]--;
        ans -= suma[1][0][R[i]] - suma[0][0][L[i]];
        L[i] = g[0][0][L[i]], R[i] = g[1][0][R[i]];
      }
    }
  }
  cout << ans;
}

```