#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;
template<class T> void assign(V<T>& v, int n, const T& a = T()) { v.assign(n, a); }
template<class T, class... Args> void assign(V<T>& v, int n, const Args&... args) { v.resize(n); for (auto&& e : v) assign(e, args...); }


constexpr lint mod = 998244353;
inline lint emod(lint a, lint p = mod) { return (a % p + p) % p; }
inline lint powm(lint a, lint n, lint p = mod) { return !n ? 1 : powm(a * a % p, n >> 1, p) * (n & 1 ? a : 1) % p; }

int main() {
  cin.tie(nullptr); ios_base::sync_with_stdio(false);
  string s; cin >> s;
  int n = s.size();
  if (n < 10) {
    set<string> vis;
    queue<string> que;
    vis.insert(s); que.push(s);
    while (!que.empty()) {
      string t = que.front(); que.pop();
      for (int i = 0; i < n - 1; ++i) if (t[i] != t[i + 1]) {
        string u = t;
        u[i] = u[i + 1] = 'a' + 3 - (t[i] - 'a') - (t[i + 1] - 'a');
        if (vis.count(u)) continue;
        vis.insert(u); que.push(u);
      }
    }
    cout << vis.size() << '\n';
  } else {
    int r = 0;
    for (char c : s) r += c - 'a';
    r %= 3;
    VV< V<lint> > dp; assign(dp, n + 1, 3, 3);
    for (int i = 0; i < 3; ++i) dp[1][i][i] = 1;
    for (int i = 1; i < n; ++i) for (int j = 0; j < 3; ++j) for (int k = 0; k < 3; ++k) {
      (dp[i + 1][(j + k + 1) % 3][(k + 1) % 3] += dp[i][j][k]) %= mod;
      (dp[i + 1][(j + k + 2) % 3][(k + 2) % 3] += dp[i][j][k]) %= mod;
    }
    lint res = powm(3, n - 1) - accumulate(begin(dp[n][r]), end(dp[n][r]), 0LL);
    if (all_of(begin(s), end(s), [&](char c) { return c == s[0]; })) return cout << 1 << '\n', 0;
    if (adjacent_find(begin(s), end(s)) == end(s)) ++res;
    cout << emod(res) << '\n';
  }
}
### Prompt

Create a solution in CPP for the following problem:

You are given a string S consisting of `a`,`b` and `c`. Find the number of strings that can be possibly obtained by repeatedly performing the following operation zero or more times, modulo 998244353:

* Choose an integer i such that 1\leq i\leq |S|-1 and the i-th and (i+1)-th characters in S are different. Replace each of the i-th and (i+1)-th characters in S with the character that differs from both of them (among `a`, `b` and `c`).

Constraints

* 2 \leq |S| \leq 2 × 10^5
* S consists of `a`, `b` and `c`.

Input

Input is given from Standard Input in the following format:


S


Output

Print the number of strings that can be possibly obtained by repeatedly performing the operation, modulo 998244353.

Examples

Input

abc


Output

3


Input

abbac


Output

65


Input

babacabac


Output

6310


Input

ababacbcacbacacbcbbcbbacbaccacbacbacba


Output

148010497

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;
template<class T> void assign(V<T>& v, int n, const T& a = T()) { v.assign(n, a); }
template<class T, class... Args> void assign(V<T>& v, int n, const Args&... args) { v.resize(n); for (auto&& e : v) assign(e, args...); }


constexpr lint mod = 998244353;
inline lint emod(lint a, lint p = mod) { return (a % p + p) % p; }
inline lint powm(lint a, lint n, lint p = mod) { return !n ? 1 : powm(a * a % p, n >> 1, p) * (n & 1 ? a : 1) % p; }

int main() {
  cin.tie(nullptr); ios_base::sync_with_stdio(false);
  string s; cin >> s;
  int n = s.size();
  if (n < 10) {
    set<string> vis;
    queue<string> que;
    vis.insert(s); que.push(s);
    while (!que.empty()) {
      string t = que.front(); que.pop();
      for (int i = 0; i < n - 1; ++i) if (t[i] != t[i + 1]) {
        string u = t;
        u[i] = u[i + 1] = 'a' + 3 - (t[i] - 'a') - (t[i + 1] - 'a');
        if (vis.count(u)) continue;
        vis.insert(u); que.push(u);
      }
    }
    cout << vis.size() << '\n';
  } else {
    int r = 0;
    for (char c : s) r += c - 'a';
    r %= 3;
    VV< V<lint> > dp; assign(dp, n + 1, 3, 3);
    for (int i = 0; i < 3; ++i) dp[1][i][i] = 1;
    for (int i = 1; i < n; ++i) for (int j = 0; j < 3; ++j) for (int k = 0; k < 3; ++k) {
      (dp[i + 1][(j + k + 1) % 3][(k + 1) % 3] += dp[i][j][k]) %= mod;
      (dp[i + 1][(j + k + 2) % 3][(k + 2) % 3] += dp[i][j][k]) %= mod;
    }
    lint res = powm(3, n - 1) - accumulate(begin(dp[n][r]), end(dp[n][r]), 0LL);
    if (all_of(begin(s), end(s), [&](char c) { return c == s[0]; })) return cout << 1 << '\n', 0;
    if (adjacent_find(begin(s), end(s)) == end(s)) ++res;
    cout << emod(res) << '\n';
  }
}
```