#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
const int MAXN = 100000;
const int MAXC = 26;
struct OneSideSolver {
  char s[MAXN + 1];
  int n;
  int nxt[MAXN + 1][MAXC];
  int who[MAXN][MAXC];
  pair<int, int> step[MAXN][MAXC];
  int diffsteps[MAXN][MAXC];
  vector<pair<int, long long>> jump[MAXN][MAXC];
  pair<int, int> normalize(int l, int r) {
    int j = -1;
    while (j + 1 < MAXC && who[r][j + 1] >= l) ++j;
    return make_pair(r, j);
  }
  void calc() {
    for (int c = (0); c < (MAXC); ++c) nxt[n][c] = n;
    for (int i = n - 1; i >= 0; --i) {
      for (int c = (0); c < (MAXC); ++c) nxt[i][c] = nxt[i + 1][c];
      nxt[i][s[i] - 'a'] = i;
    }
    for (int i = (0); i < (n); ++i) {
      for (int j = (0); j < (MAXC); ++j) who[i][j] = -1;
      int seen = 0, seencnt = 0;
      {
        int c = s[i] - 'a';
        seen |= 1 << c;
        who[i][seencnt++] = i;
      }
      if (i - 1 >= 0)
        for (int j = (0); j < (MAXC); ++j)
          if (who[i - 1][j] != -1) {
            int c = s[who[i - 1][j]] - 'a';
            if ((seen & (1 << c)) == 0) {
              seen |= 1 << c;
              who[i][seencnt++] = who[i - 1][j];
            }
          }
    }
    for (int i = (0); i < (n); ++i) {
      pair<int, int> to = make_pair(-1, -1);
      for (int j = (0); j < (MAXC); ++j) {
        if (who[i][j] == -1) break;
        int c = s[who[i][j]] - 'a';
        to.first = min(n - 1, max(to.first, nxt[i + 1][c]));
        while (to.second + 1 < MAXC &&
               who[to.first][to.second + 1] >= who[i][j])
          ++to.second;
        step[i][j] = to;
      }
    }
    for (int i = n - 1; i >= 0; --i)
      for (int j = (0); j < (MAXC); ++j) {
        if (who[i][j] == -1) break;
        pair<int, int> to = step[i][j];
        diffsteps[i][j] =
            to.first == i
                ? 0
                : 1 + (to.second == j ? diffsteps[to.first][to.second] : 0);
        jump[i][j].clear();
        if (diffsteps[i][j] != 0) {
          jump[i][j].push_back(make_pair(to.first, to.first - i));
          for (int k = 1; (1 << k) <= diffsteps[i][j]; ++k) {
            pair<int, long long> a = jump[i][j][k - 1],
                                 b = jump[a.first][j][k - 1];
            jump[i][j].push_back(make_pair(
                b.first, a.second + b.second +
                             (long long)(1 << (k - 1)) * (b.first - a.first)));
          }
        }
      }
  }
  pair<int, long long> go(pair<int, int> state, int steps) {
    int actual = min(steps, diffsteps[state.first][state.second]);
    pair<int, long long> ret = make_pair(state.first, 0LL);
    int sofar = 0;
    for (int k = ((int)(jump[ret.first][state.second]).size()) - 1; k >= 0; --k)
      if (actual & (1 << k)) {
        pair<int, long long> cur = jump[ret.first][state.second][k];
        ret.second += cur.second + (long long)sofar * (cur.first - ret.first);
        ret.first = cur.first;
        sofar += 1 << k;
      }
    assert(sofar == actual);
    if (actual < steps)
      assert(step[ret.first][state.second].first == ret.first);
    return ret;
  }
};
int n;
char s[MAXN + 1];
OneSideSolver fwd, rev;
long long solve() {
  fwd.n = n;
  for (int i = (0); i < (n); ++i) fwd.s[i] = s[i];
  fwd.s[n] = '\0';
  rev.n = n;
  for (int i = (0); i < (n); ++i) rev.s[n - i - 1] = s[i];
  rev.s[n] = '\0';
  fwd.calc();
  rev.calc();
  long long ret = 0;
  for (int i = (0); i < (n); ++i) {
    pair<int, int> fwdstate = fwd.normalize(i, i);
    pair<int, int> revstate = rev.normalize(n - i - 1, n - i - 1);
    int prevsteps = 0;
    while (fwdstate.first != n - 1 || revstate.first != n - 1) {
      int fwdsteps = fwd.diffsteps[fwdstate.first][fwdstate.second],
          revsteps = rev.diffsteps[revstate.first][revstate.second];
      int steps = min(fwdsteps == 0 ? INT_MAX : fwdsteps,
                      revsteps == 0 ? INT_MAX : revsteps);
      assert(steps > 0 && steps != INT_MAX);
      pair<int, long long> fwdres = fwd.go(fwdstate, steps);
      pair<int, long long> revres = rev.go(revstate, steps);
      ret += fwdres.second + revres.second +
             (long long)prevsteps * (fwdres.first - fwdstate.first +
                                     revres.first - revstate.first);
      fwdstate = fwd.normalize(n - revres.first - 1, fwdres.first);
      revstate = rev.normalize(n - fwdres.first - 1, revres.first);
      prevsteps += steps;
    }
  }
  return ret;
}
void run() {
  scanf("%s", s);
  n = strlen(s);
  printf("%lld\n", solve());
}
void stress() {
  int mxn = 100, mxalph = 26;
  for (int rep = (0); rep < (100000); ++rep) {
    n = rand() % mxn + 1;
    int alph = rand() % mxalph + 1;
    for (int i = (0); i < (n); ++i) s[i] = 'a' + rand() % alph;
    s[n] = '\0';
    long long have = solve();
    if (rep % 1000 == 0) printf(".");
  }
}
void stresslarge() {
  int mxalph = 26;
  for (int rep = (0); rep < (100); ++rep) {
    n = MAXN / 1;
    int alph = rand() % mxalph + 1;
    for (int i = (0); i < (n); ++i) s[i] = 'a' + rand() % alph;
    s[n] = '\0';
    long long have = solve();
    printf(".");
  }
}
int main() {
  run();
  return 0;
}

### Prompt

Please formulate 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;
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
const int MAXN = 100000;
const int MAXC = 26;
struct OneSideSolver {
  char s[MAXN + 1];
  int n;
  int nxt[MAXN + 1][MAXC];
  int who[MAXN][MAXC];
  pair<int, int> step[MAXN][MAXC];
  int diffsteps[MAXN][MAXC];
  vector<pair<int, long long>> jump[MAXN][MAXC];
  pair<int, int> normalize(int l, int r) {
    int j = -1;
    while (j + 1 < MAXC && who[r][j + 1] >= l) ++j;
    return make_pair(r, j);
  }
  void calc() {
    for (int c = (0); c < (MAXC); ++c) nxt[n][c] = n;
    for (int i = n - 1; i >= 0; --i) {
      for (int c = (0); c < (MAXC); ++c) nxt[i][c] = nxt[i + 1][c];
      nxt[i][s[i] - 'a'] = i;
    }
    for (int i = (0); i < (n); ++i) {
      for (int j = (0); j < (MAXC); ++j) who[i][j] = -1;
      int seen = 0, seencnt = 0;
      {
        int c = s[i] - 'a';
        seen |= 1 << c;
        who[i][seencnt++] = i;
      }
      if (i - 1 >= 0)
        for (int j = (0); j < (MAXC); ++j)
          if (who[i - 1][j] != -1) {
            int c = s[who[i - 1][j]] - 'a';
            if ((seen & (1 << c)) == 0) {
              seen |= 1 << c;
              who[i][seencnt++] = who[i - 1][j];
            }
          }
    }
    for (int i = (0); i < (n); ++i) {
      pair<int, int> to = make_pair(-1, -1);
      for (int j = (0); j < (MAXC); ++j) {
        if (who[i][j] == -1) break;
        int c = s[who[i][j]] - 'a';
        to.first = min(n - 1, max(to.first, nxt[i + 1][c]));
        while (to.second + 1 < MAXC &&
               who[to.first][to.second + 1] >= who[i][j])
          ++to.second;
        step[i][j] = to;
      }
    }
    for (int i = n - 1; i >= 0; --i)
      for (int j = (0); j < (MAXC); ++j) {
        if (who[i][j] == -1) break;
        pair<int, int> to = step[i][j];
        diffsteps[i][j] =
            to.first == i
                ? 0
                : 1 + (to.second == j ? diffsteps[to.first][to.second] : 0);
        jump[i][j].clear();
        if (diffsteps[i][j] != 0) {
          jump[i][j].push_back(make_pair(to.first, to.first - i));
          for (int k = 1; (1 << k) <= diffsteps[i][j]; ++k) {
            pair<int, long long> a = jump[i][j][k - 1],
                                 b = jump[a.first][j][k - 1];
            jump[i][j].push_back(make_pair(
                b.first, a.second + b.second +
                             (long long)(1 << (k - 1)) * (b.first - a.first)));
          }
        }
      }
  }
  pair<int, long long> go(pair<int, int> state, int steps) {
    int actual = min(steps, diffsteps[state.first][state.second]);
    pair<int, long long> ret = make_pair(state.first, 0LL);
    int sofar = 0;
    for (int k = ((int)(jump[ret.first][state.second]).size()) - 1; k >= 0; --k)
      if (actual & (1 << k)) {
        pair<int, long long> cur = jump[ret.first][state.second][k];
        ret.second += cur.second + (long long)sofar * (cur.first - ret.first);
        ret.first = cur.first;
        sofar += 1 << k;
      }
    assert(sofar == actual);
    if (actual < steps)
      assert(step[ret.first][state.second].first == ret.first);
    return ret;
  }
};
int n;
char s[MAXN + 1];
OneSideSolver fwd, rev;
long long solve() {
  fwd.n = n;
  for (int i = (0); i < (n); ++i) fwd.s[i] = s[i];
  fwd.s[n] = '\0';
  rev.n = n;
  for (int i = (0); i < (n); ++i) rev.s[n - i - 1] = s[i];
  rev.s[n] = '\0';
  fwd.calc();
  rev.calc();
  long long ret = 0;
  for (int i = (0); i < (n); ++i) {
    pair<int, int> fwdstate = fwd.normalize(i, i);
    pair<int, int> revstate = rev.normalize(n - i - 1, n - i - 1);
    int prevsteps = 0;
    while (fwdstate.first != n - 1 || revstate.first != n - 1) {
      int fwdsteps = fwd.diffsteps[fwdstate.first][fwdstate.second],
          revsteps = rev.diffsteps[revstate.first][revstate.second];
      int steps = min(fwdsteps == 0 ? INT_MAX : fwdsteps,
                      revsteps == 0 ? INT_MAX : revsteps);
      assert(steps > 0 && steps != INT_MAX);
      pair<int, long long> fwdres = fwd.go(fwdstate, steps);
      pair<int, long long> revres = rev.go(revstate, steps);
      ret += fwdres.second + revres.second +
             (long long)prevsteps * (fwdres.first - fwdstate.first +
                                     revres.first - revstate.first);
      fwdstate = fwd.normalize(n - revres.first - 1, fwdres.first);
      revstate = rev.normalize(n - fwdres.first - 1, revres.first);
      prevsteps += steps;
    }
  }
  return ret;
}
void run() {
  scanf("%s", s);
  n = strlen(s);
  printf("%lld\n", solve());
}
void stress() {
  int mxn = 100, mxalph = 26;
  for (int rep = (0); rep < (100000); ++rep) {
    n = rand() % mxn + 1;
    int alph = rand() % mxalph + 1;
    for (int i = (0); i < (n); ++i) s[i] = 'a' + rand() % alph;
    s[n] = '\0';
    long long have = solve();
    if (rep % 1000 == 0) printf(".");
  }
}
void stresslarge() {
  int mxalph = 26;
  for (int rep = (0); rep < (100); ++rep) {
    n = MAXN / 1;
    int alph = rand() % mxalph + 1;
    for (int i = (0); i < (n); ++i) s[i] = 'a' + rand() % alph;
    s[n] = '\0';
    long long have = solve();
    printf(".");
  }
}
int main() {
  run();
  return 0;
}

```