#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
int _max(int x, int y) {return x > y ? x : y;}
int _min(int x, int y) {return x < y ? x : y;}
const int N = 200001;
const int mod = 998244353;
int read() {
	int s = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
	return s * f;
}
void put(int x) {
	if(x < 0) x = -x, putchar('-');
	if(x >= 10) put(x / 10);
	putchar(x % 10 + '0');
}

char ss[N];
int f[N][2][3][3];

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

int pow_mod(int a, int k) {
	int ans = 1;
	while(k) {
		if(k & 1) ans = (LL)ans * a % mod;
		a = (LL)a * a % mod, k /= 2;
	} return ans;
}

int main() {
	scanf("%s", ss + 1);
	int n = strlen(ss + 1);
	if(n == 2) {
		if(ss[1] != ss[2]) puts("2");
		else puts("1");
		return 0;
	}
	bool bk = 0;
	for(int i = 1; i <= n; i++) {
		if(ss[i] != ss[1]) {bk = 1; break;}
	} if(!bk) {printf("1\n"); return 0;}
	if(n <= 3) {
		if(ss[1] != ss[2] && ss[2] != ss[3]) {
			if(ss[1] == ss[3]) puts("7");
			else puts("3");
		} else puts("6");
		return 0;
	}
	int ans = 0, cc = 1, sum = 0;
	for(int i = 1; i < n; i++) if(ss[i] == ss[i + 1]) cc = 0;
	for(int i = 1; i <= n; i++) sum += ss[i] - 'a';
	sum %= 3;
	f[1][0][0][0] = f[1][0][1][1] = f[1][0][2][2] = 1;
	for(int i = 2; i <= n; i++) {
		for(int j = 0; j < 3; j++) {
			for(int k = 0; k < 3; k++) if(f[i - 1][0][j][k] || f[i - 1][1][j][k]){
				for(int h = 0; h < 3; h++) {
					if(h == k) f[i][1][(j + h) % 3][h] = add(f[i][1][(j + h) % 3][h], f[i - 1][0][j][k]);
					else f[i][0][(j + h) % 3][h] = add(f[i][0][(j + h) % 3][h], f[i - 1][0][j][k]);
					f[i][1][(j + h) % 3][h] = add(f[i][1][(j + h) % 3][h], f[i - 1][1][j][k]);
				}
			}
		}
	} ans = add(add(f[n][1][sum][0], f[n][1][sum][1]), f[n][1][sum][2]);
	ans = add(ans, cc);
	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
#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
int _max(int x, int y) {return x > y ? x : y;}
int _min(int x, int y) {return x < y ? x : y;}
const int N = 200001;
const int mod = 998244353;
int read() {
	int s = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
	return s * f;
}
void put(int x) {
	if(x < 0) x = -x, putchar('-');
	if(x >= 10) put(x / 10);
	putchar(x % 10 + '0');
}

char ss[N];
int f[N][2][3][3];

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

int pow_mod(int a, int k) {
	int ans = 1;
	while(k) {
		if(k & 1) ans = (LL)ans * a % mod;
		a = (LL)a * a % mod, k /= 2;
	} return ans;
}

int main() {
	scanf("%s", ss + 1);
	int n = strlen(ss + 1);
	if(n == 2) {
		if(ss[1] != ss[2]) puts("2");
		else puts("1");
		return 0;
	}
	bool bk = 0;
	for(int i = 1; i <= n; i++) {
		if(ss[i] != ss[1]) {bk = 1; break;}
	} if(!bk) {printf("1\n"); return 0;}
	if(n <= 3) {
		if(ss[1] != ss[2] && ss[2] != ss[3]) {
			if(ss[1] == ss[3]) puts("7");
			else puts("3");
		} else puts("6");
		return 0;
	}
	int ans = 0, cc = 1, sum = 0;
	for(int i = 1; i < n; i++) if(ss[i] == ss[i + 1]) cc = 0;
	for(int i = 1; i <= n; i++) sum += ss[i] - 'a';
	sum %= 3;
	f[1][0][0][0] = f[1][0][1][1] = f[1][0][2][2] = 1;
	for(int i = 2; i <= n; i++) {
		for(int j = 0; j < 3; j++) {
			for(int k = 0; k < 3; k++) if(f[i - 1][0][j][k] || f[i - 1][1][j][k]){
				for(int h = 0; h < 3; h++) {
					if(h == k) f[i][1][(j + h) % 3][h] = add(f[i][1][(j + h) % 3][h], f[i - 1][0][j][k]);
					else f[i][0][(j + h) % 3][h] = add(f[i][0][(j + h) % 3][h], f[i - 1][0][j][k]);
					f[i][1][(j + h) % 3][h] = add(f[i][1][(j + h) % 3][h], f[i - 1][1][j][k]);
				}
			}
		}
	} ans = add(add(f[n][1][sum][0], f[n][1][sum][1]), f[n][1][sum][2]);
	ans = add(ans, cc);
	printf("%d\n", ans);
	return 0;
}

```