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

#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)

mt19937 Rnd(chrono::high_resolution_clock::now().time_since_epoch().count());

template <typename T>
inline void chkmax(T &x, T y) { if (x < y) x = y; }

template <typename T>
inline void chkmin(T &x, T y) { if (x > y) x = y; }

inline int read() {
  #define nc getchar()
  int x = 0;
  char c = nc;
  while (c < 48) c = nc;
  while (c > 47) x = (x << 3) + (x << 1) + (c ^ 48), c = nc;
  return x;
  #undef nc
}

const int maxn = 2e5 + 10, P = 998244353;
char str[maxn];
int n, dp[2][2][3][3];

set <int> mp;

void dfs() {
  int val = 0;
  rep(i, 1, n) {
    val = (2333ll * val + str[i]) % P;
  }
  if (mp.find(val) != mp.end()) return;
  mp.insert(val);
  rep(i, 1, n - 1) {
    if (str[i] != str[i + 1]) {
      char ch, t1 = str[i], t2 = str[i + 1];
      rep(c, 0, 2) if (t1 - 'a' != c && t2 - 'a' != c) {
        ch = c + 'a';
      }
      str[i] = str[i + 1] = ch;
      dfs();
      str[i] = t1, str[i + 1] = t2;
    }
  }
}

inline void Add(int &x, int y) {
  x += y;
  if (x >= P) x -= P;
}

int main() {
  scanf("%s", str + 1);
  n = strlen(str + 1);
  if (n <= 3) {
    dfs(), printf("%d\n", (int) mp.size());
    return 0;
  }
  int sum = 0;
  bool flg_eq = 1, flg_neq = 1;
  rep(i, 1, n) flg_eq &= str[i] == str[1], flg_neq &= i == n || str[i] != str[i + 1], sum = (sum + str[i] - 'a') % 3;
  if (flg_eq) return puts("1"), 0;
  int sel = 0;
  dp[0][0][0][0] = dp[0][0][1][1] = dp[0][0][2][2] = 1;
  rep(T, 1, n - 1) {
    memset(dp[sel ^ 1], 0, sizeof dp[sel ^ 1]);
    rep(i, 0, 2) {
      rep(j, 0, 2) {
        rep(k, 0, 2) {
          Add(dp[sel ^ 1][1][(i + k) % 3][k], dp[sel][1][i][j]);
          if (j != k) Add(dp[sel ^ 1][0][(i + k) % 3][k], dp[sel][0][i][j]);
          if (j == k) Add(dp[sel ^ 1][1][(i + k) % 3][k], dp[sel][0][i][j]);
        }
      }
    }
    sel ^= 1;
  }
  int res = flg_neq;
  rep(i, 0, 2) Add(res, dp[sel][1][sum][i]);
  printf("%d\n", res);
  return 0;
}
### Prompt

Create a solution in Cpp for 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;

#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)

mt19937 Rnd(chrono::high_resolution_clock::now().time_since_epoch().count());

template <typename T>
inline void chkmax(T &x, T y) { if (x < y) x = y; }

template <typename T>
inline void chkmin(T &x, T y) { if (x > y) x = y; }

inline int read() {
  #define nc getchar()
  int x = 0;
  char c = nc;
  while (c < 48) c = nc;
  while (c > 47) x = (x << 3) + (x << 1) + (c ^ 48), c = nc;
  return x;
  #undef nc
}

const int maxn = 2e5 + 10, P = 998244353;
char str[maxn];
int n, dp[2][2][3][3];

set <int> mp;

void dfs() {
  int val = 0;
  rep(i, 1, n) {
    val = (2333ll * val + str[i]) % P;
  }
  if (mp.find(val) != mp.end()) return;
  mp.insert(val);
  rep(i, 1, n - 1) {
    if (str[i] != str[i + 1]) {
      char ch, t1 = str[i], t2 = str[i + 1];
      rep(c, 0, 2) if (t1 - 'a' != c && t2 - 'a' != c) {
        ch = c + 'a';
      }
      str[i] = str[i + 1] = ch;
      dfs();
      str[i] = t1, str[i + 1] = t2;
    }
  }
}

inline void Add(int &x, int y) {
  x += y;
  if (x >= P) x -= P;
}

int main() {
  scanf("%s", str + 1);
  n = strlen(str + 1);
  if (n <= 3) {
    dfs(), printf("%d\n", (int) mp.size());
    return 0;
  }
  int sum = 0;
  bool flg_eq = 1, flg_neq = 1;
  rep(i, 1, n) flg_eq &= str[i] == str[1], flg_neq &= i == n || str[i] != str[i + 1], sum = (sum + str[i] - 'a') % 3;
  if (flg_eq) return puts("1"), 0;
  int sel = 0;
  dp[0][0][0][0] = dp[0][0][1][1] = dp[0][0][2][2] = 1;
  rep(T, 1, n - 1) {
    memset(dp[sel ^ 1], 0, sizeof dp[sel ^ 1]);
    rep(i, 0, 2) {
      rep(j, 0, 2) {
        rep(k, 0, 2) {
          Add(dp[sel ^ 1][1][(i + k) % 3][k], dp[sel][1][i][j]);
          if (j != k) Add(dp[sel ^ 1][0][(i + k) % 3][k], dp[sel][0][i][j]);
          if (j == k) Add(dp[sel ^ 1][1][(i + k) % 3][k], dp[sel][0][i][j]);
        }
      }
    }
    sel ^= 1;
  }
  int res = flg_neq;
  rep(i, 0, 2) Add(res, dp[sel][1][sum][i]);
  printf("%d\n", res);
  return 0;
}
```