#include <bits/stdc++.h>

using namespace std;

const int mod = 998244353;

int dp[200000][3][4][2];

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

  int sum = 0;
  int match = 0;
  for(int i = 1; i < S.size(); i++) {
    if(S[i - 1] == S[i]) ++match;
  }
  for(int i = 0; i < S.size(); i++) {
    sum += (S[i] - 'a') % 3;
  }

  if(match + 1 == S.size()) {
    cout << 1 << endl;
    return 0;
  }

  if(S.size() < 10) {
    queue< string > que;
    set< string > used;
    que.emplace(S);
    used.emplace(S);
    string tmp = "abc";
    while(que.size()) {
      string p = que.front();
      que.pop();
      for(int i = 1; i < p.size(); i++) {
        if(p[i - 1] != p[i]) {
          for(int j = 0; j < 3; j++) {
            if(p[i - 1] == tmp[j]) continue;
            if(p[i] == tmp[j]) continue;
            string q = p;
            q[i - 1] = tmp[j];
            q[i] = tmp[j];
            if(used.count(q)) continue;
            used.emplace(q);
            que.emplace(q);
          }
        }
      }
    }
    cout << used.size() << endl;
    return 0;
  }

  dp[0][0][3][0] = 1;
  for(int i = 0; i < S.size(); i++) {
    for(int j = 0; j < 3; j++) {
      for(int k = 0; k < 4; k++) {
        for(int l = 0; l < 2; l++) {
          if(dp[i][j][k][l] == 0) continue;
          for(int m = 0; m < 3; m++) {
            (dp[i + 1][(j + m) % 3][m][l | (k == m)] += dp[i][j][k][l]) %= mod;
          }
        }
      }
    }
  }
  int ans = 0;
  for(int i = 0; i < 3; i++) {
    (ans += dp[S.size()][sum % 3][i][1]) %= mod;
  }
  if(match == 0) (ans += 1) %= mod;
  cout << ans << endl;
}
### Prompt

Generate 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 <bits/stdc++.h>

using namespace std;

const int mod = 998244353;

int dp[200000][3][4][2];

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

  int sum = 0;
  int match = 0;
  for(int i = 1; i < S.size(); i++) {
    if(S[i - 1] == S[i]) ++match;
  }
  for(int i = 0; i < S.size(); i++) {
    sum += (S[i] - 'a') % 3;
  }

  if(match + 1 == S.size()) {
    cout << 1 << endl;
    return 0;
  }

  if(S.size() < 10) {
    queue< string > que;
    set< string > used;
    que.emplace(S);
    used.emplace(S);
    string tmp = "abc";
    while(que.size()) {
      string p = que.front();
      que.pop();
      for(int i = 1; i < p.size(); i++) {
        if(p[i - 1] != p[i]) {
          for(int j = 0; j < 3; j++) {
            if(p[i - 1] == tmp[j]) continue;
            if(p[i] == tmp[j]) continue;
            string q = p;
            q[i - 1] = tmp[j];
            q[i] = tmp[j];
            if(used.count(q)) continue;
            used.emplace(q);
            que.emplace(q);
          }
        }
      }
    }
    cout << used.size() << endl;
    return 0;
  }

  dp[0][0][3][0] = 1;
  for(int i = 0; i < S.size(); i++) {
    for(int j = 0; j < 3; j++) {
      for(int k = 0; k < 4; k++) {
        for(int l = 0; l < 2; l++) {
          if(dp[i][j][k][l] == 0) continue;
          for(int m = 0; m < 3; m++) {
            (dp[i + 1][(j + m) % 3][m][l | (k == m)] += dp[i][j][k][l]) %= mod;
          }
        }
      }
    }
  }
  int ans = 0;
  for(int i = 0; i < 3; i++) {
    (ans += dp[S.size()][sum % 3][i][1]) %= mod;
  }
  if(match == 0) (ans += 1) %= mod;
  cout << ans << endl;
}
```