#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10, mod = 998244353;
int f[N][3][3][2];

int add(int x, int y) {
  return (x += y) > mod ? x - mod : x;
}

void Add(int &x, int y) {
  x = add(x, y);
}

char lx[N];
int main() {
  scanf("%s", lx + 1);
  int n = strlen(lx + 1);
  int tot = 0, flg = 1, F = 1;
  for(int i = 1; i <= n; ++i) {
    int pos = lx[i] - 'a';
    tot = (tot + pos) % 3;
    if(i > 1 && lx[i] != lx[i - 1]) F = 0;
    if(i > 1 && lx[i] == lx[i - 1]) flg = 0;
  }
  if(F) {
    puts("1");
    exit(0);
  } else if(n == 2) {
    puts("2");
    exit(0);
  } else if(n == 3) {
    if(lx[1] == lx[2]) {
      puts("6");
    } else {
      if(lx[2] == lx[3]) {
        puts("6");  
      } else if(lx[3] == lx[1]) {
        puts("7");
      } else {
        puts("3");
      }
    }
    exit(0);
  }
  for(int i = 0; i < 3; ++i) f[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 t = 0; t < 2; ++t) {
          //f[i][j][k][t];
          for(int w = 0; w < 3; ++w) {
            Add(f[i + 1][(j + w) % 3][w][t | (w == k)], f[i][j][k][t]);
          }
        }
  int ans = flg;
  for(int j = 0; j < 3; ++j) 
    Add(ans, f[n][tot][j][1]);
  printf("%d\n", ans);
  return 0;
}
### Prompt

In CPP, your task is to solve 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 N = 2e5 + 10, mod = 998244353;
int f[N][3][3][2];

int add(int x, int y) {
  return (x += y) > mod ? x - mod : x;
}

void Add(int &x, int y) {
  x = add(x, y);
}

char lx[N];
int main() {
  scanf("%s", lx + 1);
  int n = strlen(lx + 1);
  int tot = 0, flg = 1, F = 1;
  for(int i = 1; i <= n; ++i) {
    int pos = lx[i] - 'a';
    tot = (tot + pos) % 3;
    if(i > 1 && lx[i] != lx[i - 1]) F = 0;
    if(i > 1 && lx[i] == lx[i - 1]) flg = 0;
  }
  if(F) {
    puts("1");
    exit(0);
  } else if(n == 2) {
    puts("2");
    exit(0);
  } else if(n == 3) {
    if(lx[1] == lx[2]) {
      puts("6");
    } else {
      if(lx[2] == lx[3]) {
        puts("6");  
      } else if(lx[3] == lx[1]) {
        puts("7");
      } else {
        puts("3");
      }
    }
    exit(0);
  }
  for(int i = 0; i < 3; ++i) f[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 t = 0; t < 2; ++t) {
          //f[i][j][k][t];
          for(int w = 0; w < 3; ++w) {
            Add(f[i + 1][(j + w) % 3][w][t | (w == k)], f[i][j][k][t]);
          }
        }
  int ans = flg;
  for(int j = 0; j < 3; ++j) 
    Add(ans, f[n][tot][j][1]);
  printf("%d\n", ans);
  return 0;
}
```