#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 bl[N + 1], br[N + 1];
  int lm[N], rm[N];
  int mxr[N];
  int lk[L][N], rk[L][N];
  int64_t sl[L][N], sr[L][N];
  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()) - 1
                                                         : pos[c][i + 1];
      }
    }
    for (int i = int(0); i < int(((int)(s).size())); ++i) {
      cl[i] = i;
      cr[i] = i;
    }
    for (int m = int(1); m < int(C + 1); ++m) {
      {
        memset(cnt, 0, sizeof cnt);
        int k = 0;
        int rb = 0;
        int b = -1;
        int dl = 0, dr = 0;
        for (int lb = int(0); lb < int(((int)(s).size())); ++lb) {
          if (lb > b) {
            b = rb;
            dl = bl[b] = ((int)(s).size());
            dr = br[b] = -1;
            for (int i = int(b) - 1; i >= int(lb); --i) {
              bl[i] = min(bl[i + 1], l[i]);
              br[i] = max(br[i + 1], r[i]);
            }
          }
          while (rb < ((int)(s).size())) {
            int &x = cnt[s[rb] - 'a'];
            if (k + !x > m) {
              break;
            }
            umn(dl, l[rb]);
            umx(dr, r[rb]);
            rm[rb] = max(br[lb], dr);
            k += !x;
            ++x;
            ++rb;
          }
          mxr[lb] = rb;
          lm[lb] = min(bl[lb], dl);
          int &x = cnt[s[lb] - 'a'];
          --x;
          k -= !x;
        }
      }
      for (int i = int(0); i < int(((int)(s).size())); ++i) {
        lk[0][i] = lm[i];
        rk[0][i] = rm[i];
        sl[0][i] = i;
        sr[0][i] = ((int)(s).size()) - i - 1;
      }
      for (int t = int(0); t < int(L - 1); ++t) {
        for (int i = int(0); i < int(((int)(s).size())); ++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 i = int(0); i < int(((int)(s).size())); ++i) {
        auto up = [&](int t) {
          ans += sl[t][cl[i]];
          ans += sr[t][cr[i]];
          cl[i] = lk[t][cl[i]];
          cr[i] = rk[t][cr[i]];
        };
        for (int t = int(L) - 1; t >= int(0); --t) {
          if (rk[t][cr[i]] < mxr[lk[t][cl[i]]]) {
            up(t);
          }
        }
        if (cr[i] < mxr[cl[i]]) {
          up(0);
        }
      }
    }
  }
  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;
}

### 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;
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 bl[N + 1], br[N + 1];
  int lm[N], rm[N];
  int mxr[N];
  int lk[L][N], rk[L][N];
  int64_t sl[L][N], sr[L][N];
  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()) - 1
                                                         : pos[c][i + 1];
      }
    }
    for (int i = int(0); i < int(((int)(s).size())); ++i) {
      cl[i] = i;
      cr[i] = i;
    }
    for (int m = int(1); m < int(C + 1); ++m) {
      {
        memset(cnt, 0, sizeof cnt);
        int k = 0;
        int rb = 0;
        int b = -1;
        int dl = 0, dr = 0;
        for (int lb = int(0); lb < int(((int)(s).size())); ++lb) {
          if (lb > b) {
            b = rb;
            dl = bl[b] = ((int)(s).size());
            dr = br[b] = -1;
            for (int i = int(b) - 1; i >= int(lb); --i) {
              bl[i] = min(bl[i + 1], l[i]);
              br[i] = max(br[i + 1], r[i]);
            }
          }
          while (rb < ((int)(s).size())) {
            int &x = cnt[s[rb] - 'a'];
            if (k + !x > m) {
              break;
            }
            umn(dl, l[rb]);
            umx(dr, r[rb]);
            rm[rb] = max(br[lb], dr);
            k += !x;
            ++x;
            ++rb;
          }
          mxr[lb] = rb;
          lm[lb] = min(bl[lb], dl);
          int &x = cnt[s[lb] - 'a'];
          --x;
          k -= !x;
        }
      }
      for (int i = int(0); i < int(((int)(s).size())); ++i) {
        lk[0][i] = lm[i];
        rk[0][i] = rm[i];
        sl[0][i] = i;
        sr[0][i] = ((int)(s).size()) - i - 1;
      }
      for (int t = int(0); t < int(L - 1); ++t) {
        for (int i = int(0); i < int(((int)(s).size())); ++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 i = int(0); i < int(((int)(s).size())); ++i) {
        auto up = [&](int t) {
          ans += sl[t][cl[i]];
          ans += sr[t][cr[i]];
          cl[i] = lk[t][cl[i]];
          cr[i] = rk[t][cr[i]];
        };
        for (int t = int(L) - 1; t >= int(0); --t) {
          if (rk[t][cr[i]] < mxr[lk[t][cl[i]]]) {
            up(t);
          }
        }
        if (cr[i] < mxr[cl[i]]) {
          up(0);
        }
      }
    }
  }
  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;
}

```