#include <bits/stdc++.h>
using namespace std;

const int maxN = 2e5 + 10, mod = 998244353;

int n;
int f[2][3][3][2];//place, sum, last, vis
char s[maxN + 1];

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

inline void work()
{
	int now = 0;
	f[now][0][0][0] = f[now][1][1][0] = f[now][2][2][0] = 1;
	for(int i = 2; i <= n; i++)
	{
		now ^= 1;
		memset(f[now], 0, sizeof(f[now]));
		for(int s = 0; s < 3; s ++)
			for(int last = 0; last < 3; last ++)
				for(int nxt = 0; nxt < 3; nxt ++)
				{
					int &f0 = f[now][ (s + nxt) % 3 ][nxt][0], &f1 = f[now][ (s + nxt) % 3 ][nxt][1];
					if(last == nxt) f1 = ADD(f1, ADD(f[now ^ 1][s][last][0], f[now ^ 1][s][last][1]));
					else f0 = ADD(f0, f[now ^ 1][s][last][0]), f1 = ADD(f1, f[now ^ 1][s][last][1]);
				}
	}

	int sum = 0, ans = 0;
	for(int i = 1; i <= n; i++) sum += (s[i] - 'a'), sum %= 3;
	for(int i = 0; i < 3; i++) ans = ADD(ans, f[now][sum][i][1]);
	int t = 1;
	for(int i = 1; i < n; i++)
		if(s[i] == s[i + 1]) t = 0;
	printf("%d\n", ADD(ans, t));
}

int main()
{
	scanf("%s", s + 1);
	n = strlen(s + 1);
	bool flag = true;
	for(int i = 2; i <= n; i++)
		if(s[i] != s[1]) flag = false;

	if(flag) { puts("1"); return 0; }
	if(n == 2) { puts("2"); return 0; }
	if(n == 3)
	{
		if(s[1] == s[2] || s[2] == s[3]) puts("6");
		else if(s[1] == s[3]) puts("7");
			else puts("3");
		return 0;
	}

	work();
	return 0;
}
### Prompt

Please provide a cpp coded solution to the problem described below:

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 = 2e5 + 10, mod = 998244353;

int n;
int f[2][3][3][2];//place, sum, last, vis
char s[maxN + 1];

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

inline void work()
{
	int now = 0;
	f[now][0][0][0] = f[now][1][1][0] = f[now][2][2][0] = 1;
	for(int i = 2; i <= n; i++)
	{
		now ^= 1;
		memset(f[now], 0, sizeof(f[now]));
		for(int s = 0; s < 3; s ++)
			for(int last = 0; last < 3; last ++)
				for(int nxt = 0; nxt < 3; nxt ++)
				{
					int &f0 = f[now][ (s + nxt) % 3 ][nxt][0], &f1 = f[now][ (s + nxt) % 3 ][nxt][1];
					if(last == nxt) f1 = ADD(f1, ADD(f[now ^ 1][s][last][0], f[now ^ 1][s][last][1]));
					else f0 = ADD(f0, f[now ^ 1][s][last][0]), f1 = ADD(f1, f[now ^ 1][s][last][1]);
				}
	}

	int sum = 0, ans = 0;
	for(int i = 1; i <= n; i++) sum += (s[i] - 'a'), sum %= 3;
	for(int i = 0; i < 3; i++) ans = ADD(ans, f[now][sum][i][1]);
	int t = 1;
	for(int i = 1; i < n; i++)
		if(s[i] == s[i + 1]) t = 0;
	printf("%d\n", ADD(ans, t));
}

int main()
{
	scanf("%s", s + 1);
	n = strlen(s + 1);
	bool flag = true;
	for(int i = 2; i <= n; i++)
		if(s[i] != s[1]) flag = false;

	if(flag) { puts("1"); return 0; }
	if(n == 2) { puts("2"); return 0; }
	if(n == 3)
	{
		if(s[1] == s[2] || s[2] == s[3]) puts("6");
		else if(s[1] == s[3]) puts("7");
			else puts("3");
		return 0;
	}

	work();
	return 0;
}
```