#include <bits/stdc++.h>
using namespace std;

const int MOD = 998244353;

string s;
vector<int> v;
int l;
int mod3_s;
map<vector<int>, bool> used;

int solve1(vector<int> now) {
  if ( used[now] ) return 0;
  used[now] = true;
  
  int ret = 1;
  for ( int i = 0; i < l-1; i++ ) {
    if ( now[i] != now[i+1] ) {
      vector<int> nxt = now;
      nxt[i] = nxt[i+1] = 3-now[i]-now[i+1];
      ret += solve1(nxt);
    }
  }
  
  return ret;
}

int dp[200001][3][4][2]; //dp[idx][mod 3][bool]
int solve2(int now, int mod3, int pre, int flag) {
  if ( now == l ) {
    if ( flag && mod3 == mod3_s ) return 1;
    else return 0;
  }
  if ( dp[now][mod3][pre][flag] >= 0 ) return dp[now][mod3][pre][flag];
  
  int ret = 0;
  for ( int i = 0; i < 3; i++) {
    ret += solve2(now+1, (mod3+i)%3, i, flag|(pre==i));
    ret %= MOD;
  }

  return dp[now][mod3][pre][flag] = ret%MOD;
}

int main() {
  cin >> s;
  l = s.size();
  for ( int i = 0; i < l; i++ ) v.push_back(s[i]-'a'), mod3_s += v[i];
  mod3_s %= 3;  

  if ( (((int)s.find("a") >= 0) + ((int)s.find("b") >= 0) + ((int)s.find("c") >= 0)) == 1 ) {
    cout << 1 << endl;
  } else if ( l <= 3 ) {
    cout << solve1(v) << endl;
  } else {
    fill_n(***dp, 200001*3*4*2, -1);
    int ans = solve2(0, 0, 3, 0);
    if ( !((int)s.find("aa") >= 0 || (int)s.find("bb") >= 0 || (int)s.find("cc") >= 0) ) ans++;
    cout << ans << endl;
  }
  
  return 0;
}

### 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;

string s;
vector<int> v;
int l;
int mod3_s;
map<vector<int>, bool> used;

int solve1(vector<int> now) {
  if ( used[now] ) return 0;
  used[now] = true;
  
  int ret = 1;
  for ( int i = 0; i < l-1; i++ ) {
    if ( now[i] != now[i+1] ) {
      vector<int> nxt = now;
      nxt[i] = nxt[i+1] = 3-now[i]-now[i+1];
      ret += solve1(nxt);
    }
  }
  
  return ret;
}

int dp[200001][3][4][2]; //dp[idx][mod 3][bool]
int solve2(int now, int mod3, int pre, int flag) {
  if ( now == l ) {
    if ( flag && mod3 == mod3_s ) return 1;
    else return 0;
  }
  if ( dp[now][mod3][pre][flag] >= 0 ) return dp[now][mod3][pre][flag];
  
  int ret = 0;
  for ( int i = 0; i < 3; i++) {
    ret += solve2(now+1, (mod3+i)%3, i, flag|(pre==i));
    ret %= MOD;
  }

  return dp[now][mod3][pre][flag] = ret%MOD;
}

int main() {
  cin >> s;
  l = s.size();
  for ( int i = 0; i < l; i++ ) v.push_back(s[i]-'a'), mod3_s += v[i];
  mod3_s %= 3;  

  if ( (((int)s.find("a") >= 0) + ((int)s.find("b") >= 0) + ((int)s.find("c") >= 0)) == 1 ) {
    cout << 1 << endl;
  } else if ( l <= 3 ) {
    cout << solve1(v) << endl;
  } else {
    fill_n(***dp, 200001*3*4*2, -1);
    int ans = solve2(0, 0, 3, 0);
    if ( !((int)s.find("aa") >= 0 || (int)s.find("bb") >= 0 || (int)s.find("cc") >= 0) ) ans++;
    cout << ans << endl;
  }
  
  return 0;
}

```