// Code by H~$~C
#include <bits/stdc++.h>
using namespace std;

static const int Maxn = 200005;
static const int mod = 998244353;

inline void inc(int &x, int y) {
  (x += y) >= mod && (x -= mod);
}

int n, ans, sum, c;
char str[Maxn];
int a[Maxn];
int dp[Maxn][3][3][2];
// , sum mod 3, the last position, has there a equal pair adjacently

namespace solve_3 {

bool vis[3][3][3];

void dfs(int a, int b, int c) {
  if (vis[a][b][c]) return ;
  vis[a][b][c] = true;
  ans++;
  if (a != b) dfs(3 - a - b, 3 - a - b, c);
  if (b != c) dfs(a, 3 - b - c, 3 - b - c);
}

int main() {
  memset(vis, false, sizeof(vis));
  ans = 0;
  dfs(a[1], a[2], a[3]);
  printf("%d\n", ans);
  return 0;
}

}

int main() {
  scanf("%s", str + 1);
  n = strlen(str + 1);
  for (int i = 1; i <= n; ++i) {
    a[i] = str[i] - 'a';
    sum += a[i];
  }
  sum %= 3;
  c = 0;
  for (int i = 1; i < n; ++i) {
    c += (a[i] == a[i + 1]);
  }
  if (c == n - 1) {
    puts("1");
    return 0;
  }
  
  if (n == 2) {
    puts("2");
    return 0;
  }
  if (n == 3) {
    solve_3::main();
    return 0;
  }
  
  for (int i = 0; i < 3; ++i) {
    dp[1][i][i][0] = 1;
  }
  for (int i = 1; i < n; ++i) {
    for (int j = 0; j < 3; ++j) {
      for (int k = 0; k < 3; ++k) {
        for (int b = 0; b < 2; ++b) {
          for (int l = 0; l < 3; ++l) {
            inc(dp[i + 1][(j + l) % 3][l][b | (l == k)], dp[i][j][k][b]);
          }
        }
      }
    }
  }
  for (int k = 0; k < 3; ++k) {
    inc(ans, dp[n][sum][k][1]);
  }
  if (c == 0) {
    inc(ans, 1);
  }
  printf("%d\n", ans);
  return 0;
}

### Prompt

Please create a solution in Cpp 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
// Code by H~$~C
#include <bits/stdc++.h>
using namespace std;

static const int Maxn = 200005;
static const int mod = 998244353;

inline void inc(int &x, int y) {
  (x += y) >= mod && (x -= mod);
}

int n, ans, sum, c;
char str[Maxn];
int a[Maxn];
int dp[Maxn][3][3][2];
// , sum mod 3, the last position, has there a equal pair adjacently

namespace solve_3 {

bool vis[3][3][3];

void dfs(int a, int b, int c) {
  if (vis[a][b][c]) return ;
  vis[a][b][c] = true;
  ans++;
  if (a != b) dfs(3 - a - b, 3 - a - b, c);
  if (b != c) dfs(a, 3 - b - c, 3 - b - c);
}

int main() {
  memset(vis, false, sizeof(vis));
  ans = 0;
  dfs(a[1], a[2], a[3]);
  printf("%d\n", ans);
  return 0;
}

}

int main() {
  scanf("%s", str + 1);
  n = strlen(str + 1);
  for (int i = 1; i <= n; ++i) {
    a[i] = str[i] - 'a';
    sum += a[i];
  }
  sum %= 3;
  c = 0;
  for (int i = 1; i < n; ++i) {
    c += (a[i] == a[i + 1]);
  }
  if (c == n - 1) {
    puts("1");
    return 0;
  }
  
  if (n == 2) {
    puts("2");
    return 0;
  }
  if (n == 3) {
    solve_3::main();
    return 0;
  }
  
  for (int i = 0; i < 3; ++i) {
    dp[1][i][i][0] = 1;
  }
  for (int i = 1; i < n; ++i) {
    for (int j = 0; j < 3; ++j) {
      for (int k = 0; k < 3; ++k) {
        for (int b = 0; b < 2; ++b) {
          for (int l = 0; l < 3; ++l) {
            inc(dp[i + 1][(j + l) % 3][l][b | (l == k)], dp[i][j][k][b]);
          }
        }
      }
    }
  }
  for (int k = 0; k < 3; ++k) {
    inc(ans, dp[n][sum][k][1]);
  }
  if (c == 0) {
    inc(ans, 1);
  }
  printf("%d\n", ans);
  return 0;
}

```