#include <iostream>
#include <set>
#include <cstring>
using namespace std;

const int64_t mod = 998244353;

int64_t PowMod(int64_t a, int64_t n) {
  int64_t p = a % mod,
          res = 1;
  while (n > 0) {
    if (n & 1) (res *= p) %= mod;
    (p *= p) %= mod;
    n >>= 1;
  }
  return res;
}

int ComputeChecksum(const string& s) {
  int sum = 0;
  for (char c : s) (sum += c - 'a') %= 3;
  return sum;
}

void BruteForce(const string& s, set<string>& strs) {
  strs.insert(s);

  for (int i = 0; i < s.size() - 1; i++) {
    if (s[i] == s[i + 1]) continue;

    string new_s = s;
    char new_c = 'a' ^ 'b' ^ 'c' ^ s[i] ^ s[i + 1];
    new_s[i] = new_s[i + 1] = new_c;

    if (!strs.count(new_s)) BruteForce(new_s, strs);
  }
}

int main() {
  string s;
  cin >> s;

  bool same_all = true,
       diff_all = true;
  for (int i = 0; i < s.size() - 1; i++) {
    same_all = same_all && (s[i] == s[i + 1]);
    diff_all = diff_all && (s[i] != s[i + 1]);
  }

  if (same_all or s.size() <= 3) {
    set<string> strs;
    BruteForce(s, strs);

    cout << strs.size() << endl;
    return 0;
  }

  static int64_t dp[200000][3][3];  // (添字, checksum, 最後に使った文字)
  memset(dp, 0, sizeof(dp));

  dp[0][0][0] = dp[0][1][1] = dp[0][2][2] = 1;

  for (int i = 0; i < s.size() - 1; i++) {
    for (int sum = 0; sum < 3; sum++) {
      for (int d = 0; d < 3; d++) {
        for (int nd = 0; nd < 3; nd++) {
          if (d == nd) continue;
          (dp[i + 1][(sum + nd) % 3][nd] += dp[i][sum][d]) %= mod;
        }
      }
    }
  }

  int checksum = ComputeChecksum(s);
  int64_t ans = PowMod(3, s.size() - 1);
  for (int d = 0; d < 3; d++) ans = (ans - dp[s.size() - 1][checksum][d] + mod) % mod;

  // 今の時点でansは少なくとも1文字は重なりがある
  if (diff_all) ans++;

  cout << ans << endl;

  return 0;
}
### Prompt

Please formulate a Cpp solution 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 <iostream>
#include <set>
#include <cstring>
using namespace std;

const int64_t mod = 998244353;

int64_t PowMod(int64_t a, int64_t n) {
  int64_t p = a % mod,
          res = 1;
  while (n > 0) {
    if (n & 1) (res *= p) %= mod;
    (p *= p) %= mod;
    n >>= 1;
  }
  return res;
}

int ComputeChecksum(const string& s) {
  int sum = 0;
  for (char c : s) (sum += c - 'a') %= 3;
  return sum;
}

void BruteForce(const string& s, set<string>& strs) {
  strs.insert(s);

  for (int i = 0; i < s.size() - 1; i++) {
    if (s[i] == s[i + 1]) continue;

    string new_s = s;
    char new_c = 'a' ^ 'b' ^ 'c' ^ s[i] ^ s[i + 1];
    new_s[i] = new_s[i + 1] = new_c;

    if (!strs.count(new_s)) BruteForce(new_s, strs);
  }
}

int main() {
  string s;
  cin >> s;

  bool same_all = true,
       diff_all = true;
  for (int i = 0; i < s.size() - 1; i++) {
    same_all = same_all && (s[i] == s[i + 1]);
    diff_all = diff_all && (s[i] != s[i + 1]);
  }

  if (same_all or s.size() <= 3) {
    set<string> strs;
    BruteForce(s, strs);

    cout << strs.size() << endl;
    return 0;
  }

  static int64_t dp[200000][3][3];  // (添字, checksum, 最後に使った文字)
  memset(dp, 0, sizeof(dp));

  dp[0][0][0] = dp[0][1][1] = dp[0][2][2] = 1;

  for (int i = 0; i < s.size() - 1; i++) {
    for (int sum = 0; sum < 3; sum++) {
      for (int d = 0; d < 3; d++) {
        for (int nd = 0; nd < 3; nd++) {
          if (d == nd) continue;
          (dp[i + 1][(sum + nd) % 3][nd] += dp[i][sum][d]) %= mod;
        }
      }
    }
  }

  int checksum = ComputeChecksum(s);
  int64_t ans = PowMod(3, s.size() - 1);
  for (int d = 0; d < 3; d++) ans = (ans - dp[s.size() - 1][checksum][d] + mod) % mod;

  // 今の時点でansは少なくとも1文字は重なりがある
  if (diff_all) ans++;

  cout << ans << endl;

  return 0;
}
```