#include <bits/stdc++.h>

using namespace std;

const int MAXN = 200200;
const int MOD = 998244353;

int N;
int dp[MAXN][3][3][2];

void add(int &x, int y) {
   x += y;
   if (x >= MOD) x -= MOD;
}

unordered_set<string> vals;

void brute(string S) {
   if (vals.count(S)) return;
   vals.emplace(S);
   for (int i = 0; i + 1 < N; ++i) {
      if (S[i] != S[i + 1]) {
         char nv = 'a' + 'b' + 'c' - S[i] - S[i + 1];
         string T = S;
         T[i] = T[i + 1] = nv;
         brute(T);
      }
   }
}

int main() {
   ios_base::sync_with_stdio(false);
   string S;
   cin >> S;
   N = S.size();
   if (N <= 7) {
      brute(S);
      cout << int(vals.size()) << "\n";
      return 0;
   }
   for (int i = 0; i < 3; ++i) {
      dp[1][i][i][0] = 1;
   }
   for (int i = 2; i <= N; ++i) {
      for (int sum = 0; sum < 3; ++sum) {
         for (int last = 0; last < 3; ++last) {
            for (int was = 0; was < 2; ++was) {
               for (int nxt = 0; nxt < 3; ++nxt) {
                  add(dp[i][(sum + nxt) % 3][nxt][was | (last == nxt)], dp[i - 1][sum][last][was]);
               }
            }
         }
      }
   }
   int sum = 0;
   bool flagDiff = true;
   bool flagSame = true;
   for (int i = 0; i < N; ++i) {
      sum += int(S[i] - 'a');
      sum %= 3;
      if (i) flagDiff &= (S[i] != S[i - 1]), flagSame &= (S[i] == S[i - 1]);
   }
   int ans = flagDiff;
   for (int i = 0; i < 3; ++i) {
      add(ans, dp[N][sum][i][1]);
   }
   if (flagSame) ans = 1;
   cout << ans << "\n";
   return 0;
}

### Prompt

Construct a cpp code solution to the problem outlined:

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 MAXN = 200200;
const int MOD = 998244353;

int N;
int dp[MAXN][3][3][2];

void add(int &x, int y) {
   x += y;
   if (x >= MOD) x -= MOD;
}

unordered_set<string> vals;

void brute(string S) {
   if (vals.count(S)) return;
   vals.emplace(S);
   for (int i = 0; i + 1 < N; ++i) {
      if (S[i] != S[i + 1]) {
         char nv = 'a' + 'b' + 'c' - S[i] - S[i + 1];
         string T = S;
         T[i] = T[i + 1] = nv;
         brute(T);
      }
   }
}

int main() {
   ios_base::sync_with_stdio(false);
   string S;
   cin >> S;
   N = S.size();
   if (N <= 7) {
      brute(S);
      cout << int(vals.size()) << "\n";
      return 0;
   }
   for (int i = 0; i < 3; ++i) {
      dp[1][i][i][0] = 1;
   }
   for (int i = 2; i <= N; ++i) {
      for (int sum = 0; sum < 3; ++sum) {
         for (int last = 0; last < 3; ++last) {
            for (int was = 0; was < 2; ++was) {
               for (int nxt = 0; nxt < 3; ++nxt) {
                  add(dp[i][(sum + nxt) % 3][nxt][was | (last == nxt)], dp[i - 1][sum][last][was]);
               }
            }
         }
      }
   }
   int sum = 0;
   bool flagDiff = true;
   bool flagSame = true;
   for (int i = 0; i < N; ++i) {
      sum += int(S[i] - 'a');
      sum %= 3;
      if (i) flagDiff &= (S[i] != S[i - 1]), flagSame &= (S[i] == S[i - 1]);
   }
   int ans = flagDiff;
   for (int i = 0; i < 3; ++i) {
      add(ans, dp[N][sum][i][1]);
   }
   if (flagSame) ans = 1;
   cout << ans << "\n";
   return 0;
}

```