#include <bits/stdc++.h>
#define P 998244353
#define MAX_N 200000
using namespace std;
template <class T> inline void read(T &x) {
	x = 0; int c = getchar(), f = 1;
	for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
	for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
char s[MAX_N+5];
int n, m, a[MAX_N+5];
int f[2][3][3][2];
bool AllSame() {
	for (int i = 1; i < n; i++)
		if (a[i] ^ a[i+1]) return false;
	return true;
}
bool AllDiff() {
	for (int i = 1; i < n; i++)
		if (a[i] == a[i+1]) return false;
	return true;
}
void Brute() {
	if (n == 2) {puts(a[1] == a[2] ? "1" : "2"); return;}
	if ((a[1]^a[2]) && (a[2]^a[3]) && (a[1]^a[3])) puts("3");
	else puts(AllSame() ? "1" : (a[1] == a[3] ? "7" : "6"));
}
void DP() {
	if (AllSame()) {puts("1"); return;}
	for (int i = 0; i < 3; i++) f[1][i][i][0] = 1;
	for (int i = 1; i <= n; i++) (m += a[i]) %= 3;
	for (int l = 1, c = 1; l <= n; l++, c ^= 1) {
		memset(f[c^1], 0, sizeof f[c^1]);
		for (int s = 0; s < 3; s++)
			for (int i = 0; i < 3; i++)
				for (int j = 0; j < 3; j++)
					(f[c^1][(s+j)%3][j][1] += f[c][s][i][1]) %= P, 
					(f[c^1][(s+j)%3][j][i==j] += f[c][s][i][0]) %= P;
	}
	int ans = AllDiff();
	for (int i = 0; i < 3; i++)
		(ans += f[n&1][m][i][1]) %= P;
	printf("%d\n", ans);
}
int main() {
	scanf("%s", s+1), n = (int)strlen(s+1);
	for (int i = 1; i <= n; i++) a[i] = s[i]-'a';
	return (n <= 3 ? Brute() : DP()), 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>
#define P 998244353
#define MAX_N 200000
using namespace std;
template <class T> inline void read(T &x) {
	x = 0; int c = getchar(), f = 1;
	for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
	for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
char s[MAX_N+5];
int n, m, a[MAX_N+5];
int f[2][3][3][2];
bool AllSame() {
	for (int i = 1; i < n; i++)
		if (a[i] ^ a[i+1]) return false;
	return true;
}
bool AllDiff() {
	for (int i = 1; i < n; i++)
		if (a[i] == a[i+1]) return false;
	return true;
}
void Brute() {
	if (n == 2) {puts(a[1] == a[2] ? "1" : "2"); return;}
	if ((a[1]^a[2]) && (a[2]^a[3]) && (a[1]^a[3])) puts("3");
	else puts(AllSame() ? "1" : (a[1] == a[3] ? "7" : "6"));
}
void DP() {
	if (AllSame()) {puts("1"); return;}
	for (int i = 0; i < 3; i++) f[1][i][i][0] = 1;
	for (int i = 1; i <= n; i++) (m += a[i]) %= 3;
	for (int l = 1, c = 1; l <= n; l++, c ^= 1) {
		memset(f[c^1], 0, sizeof f[c^1]);
		for (int s = 0; s < 3; s++)
			for (int i = 0; i < 3; i++)
				for (int j = 0; j < 3; j++)
					(f[c^1][(s+j)%3][j][1] += f[c][s][i][1]) %= P, 
					(f[c^1][(s+j)%3][j][i==j] += f[c][s][i][0]) %= P;
	}
	int ans = AllDiff();
	for (int i = 0; i < 3; i++)
		(ans += f[n&1][m][i][1]) %= P;
	printf("%d\n", ans);
}
int main() {
	scanf("%s", s+1), n = (int)strlen(s+1);
	for (int i = 1; i <= n; i++) a[i] = s[i]-'a';
	return (n <= 3 ? Brute() : DP()), 0;
}

```