#include <bits/stdc++.h>

using namespace std;

const int MOD = 998244353; 

int main() {

  string s;
  cin >> s;

  bool all_same = true;
  for (int i = 1; i < s.size(); ++i) if (s[i] != s[0]) { all_same = false; break; }
  
  if (all_same) { cout << "1" << endl; return 0; }

  if (s.size() <= 3) {
    set<string> S;
    S.insert(s);
    while (true) {
      vector<string> to_add;
      for (auto i = S.begin(); i != S.end(); ++i) {
        for (int j = 0; j < s.size() - 1; ++j) {
          if ((*i)[j] != (*i)[j + 1]) {

            bool flag[3] = { false, false, false };
            flag[(*i)[j] - 'a'] = flag[(*i)[j + 1] - 'a'] = true;
            char ch;
            for (int k = 0; k < 3; ++k) if (!flag[k]) { ch = 'a' + k; break; }

            string new_s = "";
            if (j > 0) new_s += i->substr(0, j);
            new_s += ch;
            new_s += ch;
            if (j + 2 < s.size()) new_s += i->substr(j +  2);
            to_add.push_back(new_s);
          }
        }
      }
      int pre = S.size();
      for (auto i = to_add.begin(); i != to_add.end(); ++i) S.insert(*i);
      int cur = S.size();
      if (pre == cur) break;
    }
    cout << S.size() << endl;
    return 0;
  }

  int mod = 0;
  for (int i = 0; i < s.size(); ++i) {
    mod = (mod + s[i] - 'a') % 3;
  }
 
  long long f[2][3][3][2];
  memset(f, 0x00, sizeof(f));
  int x = 0, y = 1;

  for (int d = 0; d < 3; ++d) f[x][d][d][0] = 1;

  for (int i = 1; i < s.size(); ++i, swap(x, y)) {
    for (int m = 0; m < 3; ++m) {
      for (int d = 0; d < 3; ++d) {
        for (int t = 0; t < 2; ++t) {
          f[y][m][d][t] = 0;
        }
      }
    }
 
    for (int m = 0; m < 3; ++m) {
      for (int d = 0; d < 3; ++d) {
        for (int t = 0; t < 2; ++t) {
          for (int n_d = 0; n_d < 3; ++n_d) {
            int n_m = (m + n_d) % 3;
            int n_t = (t == 1 || n_d == d) ? 1 : 0;
            f[y][n_m][n_d][n_t] = (f[y][n_m][n_d][n_t] + f[x][m][d][t]) % MOD;
          }
        }
      }
    }

  }

  long long ans = 0;
  for (int d = 0; d < 3; ++d) ans = (ans + f[x][mod][d][1]) % MOD; 

  bool all_diff = true;
  for (int i = 1; i < s.size(); ++i) if (s[i] == s[i - 1]) { all_diff = false; break; }

  if (all_diff) ans = (ans + 1) % MOD;
  
  cout << ans << endl;

  return 0;
}
### Prompt

Please create a solution in Cpp to 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;

const int MOD = 998244353; 

int main() {

  string s;
  cin >> s;

  bool all_same = true;
  for (int i = 1; i < s.size(); ++i) if (s[i] != s[0]) { all_same = false; break; }
  
  if (all_same) { cout << "1" << endl; return 0; }

  if (s.size() <= 3) {
    set<string> S;
    S.insert(s);
    while (true) {
      vector<string> to_add;
      for (auto i = S.begin(); i != S.end(); ++i) {
        for (int j = 0; j < s.size() - 1; ++j) {
          if ((*i)[j] != (*i)[j + 1]) {

            bool flag[3] = { false, false, false };
            flag[(*i)[j] - 'a'] = flag[(*i)[j + 1] - 'a'] = true;
            char ch;
            for (int k = 0; k < 3; ++k) if (!flag[k]) { ch = 'a' + k; break; }

            string new_s = "";
            if (j > 0) new_s += i->substr(0, j);
            new_s += ch;
            new_s += ch;
            if (j + 2 < s.size()) new_s += i->substr(j +  2);
            to_add.push_back(new_s);
          }
        }
      }
      int pre = S.size();
      for (auto i = to_add.begin(); i != to_add.end(); ++i) S.insert(*i);
      int cur = S.size();
      if (pre == cur) break;
    }
    cout << S.size() << endl;
    return 0;
  }

  int mod = 0;
  for (int i = 0; i < s.size(); ++i) {
    mod = (mod + s[i] - 'a') % 3;
  }
 
  long long f[2][3][3][2];
  memset(f, 0x00, sizeof(f));
  int x = 0, y = 1;

  for (int d = 0; d < 3; ++d) f[x][d][d][0] = 1;

  for (int i = 1; i < s.size(); ++i, swap(x, y)) {
    for (int m = 0; m < 3; ++m) {
      for (int d = 0; d < 3; ++d) {
        for (int t = 0; t < 2; ++t) {
          f[y][m][d][t] = 0;
        }
      }
    }
 
    for (int m = 0; m < 3; ++m) {
      for (int d = 0; d < 3; ++d) {
        for (int t = 0; t < 2; ++t) {
          for (int n_d = 0; n_d < 3; ++n_d) {
            int n_m = (m + n_d) % 3;
            int n_t = (t == 1 || n_d == d) ? 1 : 0;
            f[y][n_m][n_d][n_t] = (f[y][n_m][n_d][n_t] + f[x][m][d][t]) % MOD;
          }
        }
      }
    }

  }

  long long ans = 0;
  for (int d = 0; d < 3; ++d) ans = (ans + f[x][mod][d][1]) % MOD; 

  bool all_diff = true;
  for (int i = 1; i < s.size(); ++i) if (s[i] == s[i - 1]) { all_diff = false; break; }

  if (all_diff) ans = (ans + 1) % MOD;
  
  cout << ans << endl;

  return 0;
}
```