#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int mod = 998244353;
int n, f[2][3][3][2], nw = 1, pst = 0;
char s[2000010];

int main() {
	scanf("%s", s + 1); n = strlen(s + 1);
	for (int i = 0; i < 3; i++)f[nw][i][i][0] = 1;
	for (int t = 2; t <= n; t++) {
		swap(nw, pst);
		memset(f[nw], 0, sizeof(f[nw]));
		for (int i = 0; i < 3; i++)for (int j = 0; j < 3; j++)for (int k = 0; k < 2; k++) {
			for (int cur = 0; cur < 3; cur++) {
				(f[nw][(i + cur) % 3][cur][(j == cur) | k] += f[pst][i][j][k]) %= 998244353;
			}
		}
	}
	int tot = 0, ans = 1, flag = 0;
	for (int i = 1; i <= n; i++) {
		tot += s[i] - 'a'; tot %= 3;
		if (i > 1 && s[i] != s[i - 1])flag = 1;
		if (i > 1 && s[i] == s[i - 1])ans = 0;
	}
	if (flag == 0) { puts("1"); return 0; }
	if (n == 2) { puts("2"); return 0; }
	if (n == 3) {
		if (s[1] == s[2])puts("6");
		else {
			if (s[2] == s[3])puts("6");
			else if (s[3] == s[1])puts("7");
			else puts("3");
		}
		return 0;
	}
	for (int i = 0; i < 3; i++)(ans += f[nw][tot][i][1]) %= 998244353;
	cout << ans << endl;

	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<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int mod = 998244353;
int n, f[2][3][3][2], nw = 1, pst = 0;
char s[2000010];

int main() {
	scanf("%s", s + 1); n = strlen(s + 1);
	for (int i = 0; i < 3; i++)f[nw][i][i][0] = 1;
	for (int t = 2; t <= n; t++) {
		swap(nw, pst);
		memset(f[nw], 0, sizeof(f[nw]));
		for (int i = 0; i < 3; i++)for (int j = 0; j < 3; j++)for (int k = 0; k < 2; k++) {
			for (int cur = 0; cur < 3; cur++) {
				(f[nw][(i + cur) % 3][cur][(j == cur) | k] += f[pst][i][j][k]) %= 998244353;
			}
		}
	}
	int tot = 0, ans = 1, flag = 0;
	for (int i = 1; i <= n; i++) {
		tot += s[i] - 'a'; tot %= 3;
		if (i > 1 && s[i] != s[i - 1])flag = 1;
		if (i > 1 && s[i] == s[i - 1])ans = 0;
	}
	if (flag == 0) { puts("1"); return 0; }
	if (n == 2) { puts("2"); return 0; }
	if (n == 3) {
		if (s[1] == s[2])puts("6");
		else {
			if (s[2] == s[3])puts("6");
			else if (s[3] == s[1])puts("7");
			else puts("3");
		}
		return 0;
	}
	for (int i = 0; i < 3; i++)(ans += f[nw][tot][i][1]) %= 998244353;
	cout << ans << endl;

	return 0;
}
```