#include<bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
const int P = 998244353;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
template <typename T> void write(T x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
	write(x);
	puts("");
}
int n; char s[MAXN];
int dp[MAXN][2][3][3];
bool AllTheSame() {
	for (int i = 1; i <= n; i++)
		if (s[i] != s[1]) return false;
	return true;
}
bool NotAdjSame() {
	for (int i = 2; i <= n; i++)
		if (s[i] == s[i - 1]) return false;
	return true;
}
void update(int &x, int y) {
	x = (x + y) % P;
}
int main() {
	scanf("%s", s + 1);
	n = strlen(s + 1);
	if (AllTheSame()) {
		writeln(1);
		return 0;
	}
	if (n <= 3) {
		if (n == 2) writeln(2);
		else if (s[1] != s[2] && s[1] != s[3] && s[2] != s[3]) writeln(3);
		else if (s[1] == s[3]) writeln(7);
		else writeln(6);
		return 0;
	}
	for (int i = 0; i <= 2; i++)
		dp[1][0][i][i] = 1;
	for (int i = 2; i <= n; i++) {
		for (int e = 0; e <= 1; e++)
		for (int s = 0; s <= 2; s++)
		for (int f = 0; f <= 2; f++)
		for (int j = 0; j <= 2; j++)
			update(dp[i][e | (f == j)][(s + j) % 3][j], dp[i - 1][e][s][f]);
	}
	int ans = 0, sum = 0;
	for (int i = 1; i <= n; i++)
		sum = (sum + s[i] - 'a') % 3;
	for (int i = 0; i <= 2; i++)
		update(ans, dp[n][1][sum][i]);
	update(ans, NotAdjSame());
	writeln(ans);
	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;
const int MAXN = 200005;
const int P = 998244353;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
template <typename T> void write(T x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
	write(x);
	puts("");
}
int n; char s[MAXN];
int dp[MAXN][2][3][3];
bool AllTheSame() {
	for (int i = 1; i <= n; i++)
		if (s[i] != s[1]) return false;
	return true;
}
bool NotAdjSame() {
	for (int i = 2; i <= n; i++)
		if (s[i] == s[i - 1]) return false;
	return true;
}
void update(int &x, int y) {
	x = (x + y) % P;
}
int main() {
	scanf("%s", s + 1);
	n = strlen(s + 1);
	if (AllTheSame()) {
		writeln(1);
		return 0;
	}
	if (n <= 3) {
		if (n == 2) writeln(2);
		else if (s[1] != s[2] && s[1] != s[3] && s[2] != s[3]) writeln(3);
		else if (s[1] == s[3]) writeln(7);
		else writeln(6);
		return 0;
	}
	for (int i = 0; i <= 2; i++)
		dp[1][0][i][i] = 1;
	for (int i = 2; i <= n; i++) {
		for (int e = 0; e <= 1; e++)
		for (int s = 0; s <= 2; s++)
		for (int f = 0; f <= 2; f++)
		for (int j = 0; j <= 2; j++)
			update(dp[i][e | (f == j)][(s + j) % 3][j], dp[i - 1][e][s][f]);
	}
	int ans = 0, sum = 0;
	for (int i = 1; i <= n; i++)
		sum = (sum + s[i] - 'a') % 3;
	for (int i = 0; i <= 2; i++)
		update(ans, dp[n][1][sum][i]);
	update(ans, NotAdjSame());
	writeln(ans);
	return 0;
}
```