#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 200000 + 100, MOD = 998244353;
int N, K; char s[maxn]; ll f[maxn][3][3][2]; bool fl = true;

bool check()
{
	for(int i = 1; i < N; ++i)
		if(s[i] != s[i+1]) return false;
	return true;
}

void Init()
{
	scanf("%s", s+1);
	N = strlen(s+1), K = 0;
	for(int i = 1; i <= N; ++i)
		K = (K + s[i] - 'a') % 3;
	for(int i = 1; i < N; ++i)
		if(s[i] == s[i+1]) { fl = false; break; }
}

void Solve()
{
	if(check()) { printf("1\n"); return; }
	if(N == 3)
	{
		if(s[1]!=s[2] && s[2]!=s[3] && s[1]!=s[3]) { printf("3\n"); return; }
		if((s[1]==s[2]&&s[2]!=s[3]) || (s[1]!=s[2]&&s[2]==s[3])) { printf("6\n"); return; }
		if(s[1]==s[3] && s[1]!=s[2]) { printf("7\n"); return; }
		if(s[1]==s[2] && s[2]==s[3]) { printf("1\n"); return; }
	}
	//f[i][j][k][p]±íÊ¾Ç°iÎ» µÚiÎ»Îªj Ç°iÎ»ºÍÄ£3Îªk ³öÏÖ/Î´³öÏÖ¹ýÁ½¸öÁ¬×ÅÏàµÈµÄÇé¿öµÄ ·½°¸Êý 
	memset(f, 0, sizeof(f));
	f[1][0][0][0] = f[1][1][1][0] = f[1][2][2][0] = 1;
	for(int i = 2; i <= N; ++i)
		for(int j = 0; j <= 2; ++j) // ÕâÒ»Î»ÊÇj 
			for(int k = 0; k <= 2; ++k) // ÉÏÒ»Î»ÊÇk 
				for(int p = 0; p <= 2; ++p) // Ö®Ç°ËùÓÐºÍÎªp 
					if(f[i-1][k][p][0] || f[i-1][k][p][1])
					{
						int u = (p + j) % 3;
						if(j != k) (f[i][j][u][1] += f[i-1][k][p][1]) %= MOD, (f[i][j][u][0] += f[i-1][k][p][0]) %= MOD;
						else (f[i][j][u][1] += f[i-1][k][p][0] + f[i-1][k][p][1]) %= MOD;
					}
	printf("%lld\n", (f[N][0][K][1]+f[N][1][K][1]+f[N][2][K][1]+fl)%MOD);
}

int main()
{
	Init(), Solve();
}
### Prompt

Please formulate a Cpp solution 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<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 200000 + 100, MOD = 998244353;
int N, K; char s[maxn]; ll f[maxn][3][3][2]; bool fl = true;

bool check()
{
	for(int i = 1; i < N; ++i)
		if(s[i] != s[i+1]) return false;
	return true;
}

void Init()
{
	scanf("%s", s+1);
	N = strlen(s+1), K = 0;
	for(int i = 1; i <= N; ++i)
		K = (K + s[i] - 'a') % 3;
	for(int i = 1; i < N; ++i)
		if(s[i] == s[i+1]) { fl = false; break; }
}

void Solve()
{
	if(check()) { printf("1\n"); return; }
	if(N == 3)
	{
		if(s[1]!=s[2] && s[2]!=s[3] && s[1]!=s[3]) { printf("3\n"); return; }
		if((s[1]==s[2]&&s[2]!=s[3]) || (s[1]!=s[2]&&s[2]==s[3])) { printf("6\n"); return; }
		if(s[1]==s[3] && s[1]!=s[2]) { printf("7\n"); return; }
		if(s[1]==s[2] && s[2]==s[3]) { printf("1\n"); return; }
	}
	//f[i][j][k][p]±íÊ¾Ç°iÎ» µÚiÎ»Îªj Ç°iÎ»ºÍÄ£3Îªk ³öÏÖ/Î´³öÏÖ¹ýÁ½¸öÁ¬×ÅÏàµÈµÄÇé¿öµÄ ·½°¸Êý 
	memset(f, 0, sizeof(f));
	f[1][0][0][0] = f[1][1][1][0] = f[1][2][2][0] = 1;
	for(int i = 2; i <= N; ++i)
		for(int j = 0; j <= 2; ++j) // ÕâÒ»Î»ÊÇj 
			for(int k = 0; k <= 2; ++k) // ÉÏÒ»Î»ÊÇk 
				for(int p = 0; p <= 2; ++p) // Ö®Ç°ËùÓÐºÍÎªp 
					if(f[i-1][k][p][0] || f[i-1][k][p][1])
					{
						int u = (p + j) % 3;
						if(j != k) (f[i][j][u][1] += f[i-1][k][p][1]) %= MOD, (f[i][j][u][0] += f[i-1][k][p][0]) %= MOD;
						else (f[i][j][u][1] += f[i-1][k][p][0] + f[i-1][k][p][1]) %= MOD;
					}
	printf("%lld\n", (f[N][0][K][1]+f[N][1][K][1]+f[N][2][K][1]+fl)%MOD);
}

int main()
{
	Init(), Solve();
}
```