#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int S = 28;
const int LG = 17;
int last[S], prv[N], nxt[N], lst[N][S], L[N][S], R[N][S], cnt[N], lp[N], rp[N],
    pl[LG][N], pr[LG][N];
long long sumL[LG][N], sumR[LG][N];
vector<int> vec;
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  string s;
  cin >> s;
  int n = s.size();
  s = '.' + s;
  fill(last, last + S, 1);
  for (int i = 1; i <= n; i++) prv[i] = last[s[i] - 'a'], last[s[i] - 'a'] = i;
  fill(last, last + S, n);
  for (int i = n; i; i--) nxt[i] = last[s[i] - 'a'], last[s[i] - 'a'] = i;
  fill(last, last + S, 0);
  for (int i = 1; i <= n; i++) {
    vec.clear();
    last[s[i] - 'a'] = i;
    for (int j = 0; j < S; j++)
      if (last[j]) vec.push_back(last[j]);
    sort(vec.begin(), vec.end());
    reverse(vec.begin(), vec.end());
    lst[i][0] = n + 1;
    for (int j = 0; j < (int)(vec.size()); j++) lst[i][j + 1] = vec[j];
    R[i][0] = i;
    for (int j = 0; j + 1 < S; j++)
      R[i][j + 1] = max(R[i][j], (j < (int)(vec.size()) ? nxt[vec[j]] : i));
  }
  fill(last, last + S, n + 1);
  for (int i = n; i; i--) {
    vec.clear();
    last[s[i] - 'a'] = i;
    for (int j = 0; j < S; j++)
      if (last[j] <= n) vec.push_back(last[j]);
    sort(vec.begin(), vec.end());
    L[i][0] = i;
    for (int j = 0; j + 1 < S; j++)
      L[i][j + 1] = min(L[i][j], (j < (int)(vec.size()) ? prv[vec[j]] : i));
  }
  long long ans = 0;
  for (int i = 1; i <= n; i++) lp[i] = rp[i] = i;
  for (int c = 1; c < S; c++) {
    for (int i = 1; i <= n; i++) {
      sumL[0][i] = pl[0][i] = L[i][c];
      sumR[0][i] = pr[0][i] = R[i][c];
    }
    for (int j = 1; j < LG; j++) {
      for (int i = 1; i <= n; i++) {
        sumL[j][i] = sumL[j - 1][i] + sumL[j - 1][pl[j - 1][i]];
        pl[j][i] = pl[j - 1][pl[j - 1][i]];
        sumR[j][i] = sumR[j - 1][i] + sumR[j - 1][pr[j - 1][i]];
        pr[j][i] = pr[j - 1][pr[j - 1][i]];
      }
    }
    for (int i = 1; i <= n; i++) {
      if (!((lp[i] != 1 || rp[i] != n) && lst[rp[i]][c + 1] < lp[i])) continue;
      int nl = lp[i], nr = rp[i];
      for (int j = LG - 1; j >= 0; j--) {
        if ((pl[j][nl] != 1 || pr[j][nr] != n) &&
            lst[pr[j][nr]][c + 1] < pl[j][nl]) {
          cnt[i] += (1 << j);
          ans += sumL[j][nl] - sumR[j][nr];
          nl = pl[j][nl];
          nr = pr[j][nr];
        }
      }
      cnt[i]++;
      ans += sumL[0][nl] - sumR[0][nr];
      nl = pl[0][nl];
      nr = pr[0][nr];
      lp[i] = nl;
      rp[i] = nr;
    }
  }
  for (int i = 1; i <= n; i++) ans += 1LL * (cnt[i] + 1) * (n - 1);
  cout << ans;
  return 0;
}

### Prompt

Your task is to create a CPP solution to 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 N = 1e5 + 10;
const int S = 28;
const int LG = 17;
int last[S], prv[N], nxt[N], lst[N][S], L[N][S], R[N][S], cnt[N], lp[N], rp[N],
    pl[LG][N], pr[LG][N];
long long sumL[LG][N], sumR[LG][N];
vector<int> vec;
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  string s;
  cin >> s;
  int n = s.size();
  s = '.' + s;
  fill(last, last + S, 1);
  for (int i = 1; i <= n; i++) prv[i] = last[s[i] - 'a'], last[s[i] - 'a'] = i;
  fill(last, last + S, n);
  for (int i = n; i; i--) nxt[i] = last[s[i] - 'a'], last[s[i] - 'a'] = i;
  fill(last, last + S, 0);
  for (int i = 1; i <= n; i++) {
    vec.clear();
    last[s[i] - 'a'] = i;
    for (int j = 0; j < S; j++)
      if (last[j]) vec.push_back(last[j]);
    sort(vec.begin(), vec.end());
    reverse(vec.begin(), vec.end());
    lst[i][0] = n + 1;
    for (int j = 0; j < (int)(vec.size()); j++) lst[i][j + 1] = vec[j];
    R[i][0] = i;
    for (int j = 0; j + 1 < S; j++)
      R[i][j + 1] = max(R[i][j], (j < (int)(vec.size()) ? nxt[vec[j]] : i));
  }
  fill(last, last + S, n + 1);
  for (int i = n; i; i--) {
    vec.clear();
    last[s[i] - 'a'] = i;
    for (int j = 0; j < S; j++)
      if (last[j] <= n) vec.push_back(last[j]);
    sort(vec.begin(), vec.end());
    L[i][0] = i;
    for (int j = 0; j + 1 < S; j++)
      L[i][j + 1] = min(L[i][j], (j < (int)(vec.size()) ? prv[vec[j]] : i));
  }
  long long ans = 0;
  for (int i = 1; i <= n; i++) lp[i] = rp[i] = i;
  for (int c = 1; c < S; c++) {
    for (int i = 1; i <= n; i++) {
      sumL[0][i] = pl[0][i] = L[i][c];
      sumR[0][i] = pr[0][i] = R[i][c];
    }
    for (int j = 1; j < LG; j++) {
      for (int i = 1; i <= n; i++) {
        sumL[j][i] = sumL[j - 1][i] + sumL[j - 1][pl[j - 1][i]];
        pl[j][i] = pl[j - 1][pl[j - 1][i]];
        sumR[j][i] = sumR[j - 1][i] + sumR[j - 1][pr[j - 1][i]];
        pr[j][i] = pr[j - 1][pr[j - 1][i]];
      }
    }
    for (int i = 1; i <= n; i++) {
      if (!((lp[i] != 1 || rp[i] != n) && lst[rp[i]][c + 1] < lp[i])) continue;
      int nl = lp[i], nr = rp[i];
      for (int j = LG - 1; j >= 0; j--) {
        if ((pl[j][nl] != 1 || pr[j][nr] != n) &&
            lst[pr[j][nr]][c + 1] < pl[j][nl]) {
          cnt[i] += (1 << j);
          ans += sumL[j][nl] - sumR[j][nr];
          nl = pl[j][nl];
          nr = pr[j][nr];
        }
      }
      cnt[i]++;
      ans += sumL[0][nl] - sumR[0][nr];
      nl = pl[0][nl];
      nr = pr[0][nr];
      lp[i] = nl;
      rp[i] = nr;
    }
  }
  for (int i = 1; i <= n; i++) ans += 1LL * (cnt[i] + 1) * (n - 1);
  cout << ans;
  return 0;
}

```