#include <algorithm>
#include <bitset>
#include <cassert>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<unsigned char, unsigned char> pcc;
typedef pair<double, double> pdd;
typedef vector<vector<ll>> matrix;

void dfs(set<string>& ret, string s) {
  if(ret.count(s)) return;
  ret.insert(s);
  for(int i = 0; i + 1 < s.size(); i++) {
    if(s[i] == s[i+1]) continue;
    char ch = 'a';
    while(s[i] == ch || s[i+1] == ch) ch++;
    dfs(ret, s.substr(0, i) + ch + "" + ch + "" + s.substr(i+2, s.size()-i-2));
  }
}

void bruteforce(string s) {
  set<string> ret;
  dfs(ret, s);
  cout << ret.size() << "\n";
  exit(0);
}

int dp[3][3][2];
int ndp[3][3][2];
const int MOD = 998244353;
void solve() {
  string s;
  cin >> s;
  if(s.size() <= 6) {
    bruteforce(s);
  }
  bool allSame = true;
  for(int i = 1; i < s.size(); i++) {
    allSame &= s[i] == s[i-1];
  }
  if(allSame) {
    cout << "1\n";
    return;
  }
  int sum = 0;
  bool allDistinct = true;
  for(int i = 0; i + 1 < s.size(); i++) {
    if(s[i] == s[i+1]) allDistinct = false;
  }
  for(int i = 0; i < s.size(); i++) {
    sum += s[i] - 'a';
  }
  sum %= 3;
  for(int x = 0; x < 3; x++) {
    dp[x][x][0] = 1;
  }
  for(int qq = 1; qq < s.size(); qq++) {
    memset(ndp, 0, sizeof(ndp));
    for(int i = 0; i < 3; i++) {
      for(int j = 0; j < 3; j++) {
        for(int k = 0; k < 2; k++) {
          for(int a = 0; a < 3; a++) {
            ndp[(i+a)%3][a][k | (j == a)] += dp[i][j][k];
            ndp[(i+a)%3][a][k | (j == a)] %= MOD;
          }
        }
      }
    }
    memcpy(dp, ndp, sizeof(dp));
  }
  int ret = allDistinct;
  ret += dp[sum][0][1];
  ret %= MOD;
  ret += dp[sum][1][1];
  ret %= MOD;
  ret += dp[sum][2][1];
  ret %= MOD;
  cout << ret << "\n";
}

void casesolve() {
  int t;
  cin >> t;
  for(int i = 1; i <= t; i++) {
    cout << "Case #" << i << ":" << "\n";
    solve();
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  solve();
  // casesolve();
}

### 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 <algorithm>
#include <bitset>
#include <cassert>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<unsigned char, unsigned char> pcc;
typedef pair<double, double> pdd;
typedef vector<vector<ll>> matrix;

void dfs(set<string>& ret, string s) {
  if(ret.count(s)) return;
  ret.insert(s);
  for(int i = 0; i + 1 < s.size(); i++) {
    if(s[i] == s[i+1]) continue;
    char ch = 'a';
    while(s[i] == ch || s[i+1] == ch) ch++;
    dfs(ret, s.substr(0, i) + ch + "" + ch + "" + s.substr(i+2, s.size()-i-2));
  }
}

void bruteforce(string s) {
  set<string> ret;
  dfs(ret, s);
  cout << ret.size() << "\n";
  exit(0);
}

int dp[3][3][2];
int ndp[3][3][2];
const int MOD = 998244353;
void solve() {
  string s;
  cin >> s;
  if(s.size() <= 6) {
    bruteforce(s);
  }
  bool allSame = true;
  for(int i = 1; i < s.size(); i++) {
    allSame &= s[i] == s[i-1];
  }
  if(allSame) {
    cout << "1\n";
    return;
  }
  int sum = 0;
  bool allDistinct = true;
  for(int i = 0; i + 1 < s.size(); i++) {
    if(s[i] == s[i+1]) allDistinct = false;
  }
  for(int i = 0; i < s.size(); i++) {
    sum += s[i] - 'a';
  }
  sum %= 3;
  for(int x = 0; x < 3; x++) {
    dp[x][x][0] = 1;
  }
  for(int qq = 1; qq < s.size(); qq++) {
    memset(ndp, 0, sizeof(ndp));
    for(int i = 0; i < 3; i++) {
      for(int j = 0; j < 3; j++) {
        for(int k = 0; k < 2; k++) {
          for(int a = 0; a < 3; a++) {
            ndp[(i+a)%3][a][k | (j == a)] += dp[i][j][k];
            ndp[(i+a)%3][a][k | (j == a)] %= MOD;
          }
        }
      }
    }
    memcpy(dp, ndp, sizeof(dp));
  }
  int ret = allDistinct;
  ret += dp[sum][0][1];
  ret %= MOD;
  ret += dp[sum][1][1];
  ret %= MOD;
  ret += dp[sum][2][1];
  ret %= MOD;
  cout << ret << "\n";
}

void casesolve() {
  int t;
  cin >> t;
  for(int i = 1; i <= t; i++) {
    cout << "Case #" << i << ":" << "\n";
    solve();
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  solve();
  // casesolve();
}

```