#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int INF=998244353;
char a[202020];
int f[202020][3][3][2];
int main()
{
	int n,sum,pp,i,j,k,l,ans=0,lt;
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	scanf("%s",a+1);
	n=strlen(a+1);
	if(n<4)
	{
		if(n==1)
		{
			printf("1");
			return 0;
		}
		if(n==2)
		{
			if(a[1]==a[2])
				printf("1");
			else
				printf("2");
			return 0;
		}
		if(a[1]==a[2]||a[2]==a[3])
		{
			if(a[1]==a[2]&&a[2]==a[3])
				ans=1;
			else
				ans=6;
		}
		else
		{
			if(a[1]==a[3])
				ans=7;
			else
				ans=3;
		}
		printf("%d\n",ans);
		return 0;
	}
	sum=0,pp=0;
	for(i=2;i<=n;i++)
	{
		if(a[i]==a[i-1])
			sum++;
		pp+=a[i]-'a';
	}
	pp+=a[1]-'a';
	pp%=3;
	if(sum==n-1)
	{
		printf("1");
		return 0;
	}
	if(sum==0)
		ans++;
	//f[0][0][0][0]=1;
	for(i=0;i<=2;i++)
		f[1][i][i][0]=1;
	for(i=2;i<=n;i++)
	{
		for(j=0;j<=2;j++)
		{
			for(k=0;k<=2;k++)
			{
				for(l=0;l<=2;l++)
				{
					lt=j-k;
					if(lt<0)
						lt+=3;
					if(k==l)
					{
						f[i][j][k][1]=(f[i][j][k][1]+f[i-1][lt][l][0])%INF;
						f[i][j][k][1]=(f[i][j][k][1]+f[i-1][lt][l][1])%INF;
					}
					else
					{
						f[i][j][k][0]=(f[i][j][k][0]+f[i-1][lt][l][0])%INF;
						f[i][j][k][1]=(f[i][j][k][1]+f[i-1][lt][l][1])%INF;
					}
				}
			//	printf("%d %d %d %d %d %d\n",i,j,k,l,f[i][j][k][0],f[i][j][k][1]);
			}
		}
	}
	for(i=0;i<=2;i++)
	{
		ans=(ans+f[n][pp][i][1])%INF;
	}
	printf("%d\n",ans);
	return 0;
}

### Prompt

Your task is to create 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<vector>
#include<algorithm>
using namespace std;
const int INF=998244353;
char a[202020];
int f[202020][3][3][2];
int main()
{
	int n,sum,pp,i,j,k,l,ans=0,lt;
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	scanf("%s",a+1);
	n=strlen(a+1);
	if(n<4)
	{
		if(n==1)
		{
			printf("1");
			return 0;
		}
		if(n==2)
		{
			if(a[1]==a[2])
				printf("1");
			else
				printf("2");
			return 0;
		}
		if(a[1]==a[2]||a[2]==a[3])
		{
			if(a[1]==a[2]&&a[2]==a[3])
				ans=1;
			else
				ans=6;
		}
		else
		{
			if(a[1]==a[3])
				ans=7;
			else
				ans=3;
		}
		printf("%d\n",ans);
		return 0;
	}
	sum=0,pp=0;
	for(i=2;i<=n;i++)
	{
		if(a[i]==a[i-1])
			sum++;
		pp+=a[i]-'a';
	}
	pp+=a[1]-'a';
	pp%=3;
	if(sum==n-1)
	{
		printf("1");
		return 0;
	}
	if(sum==0)
		ans++;
	//f[0][0][0][0]=1;
	for(i=0;i<=2;i++)
		f[1][i][i][0]=1;
	for(i=2;i<=n;i++)
	{
		for(j=0;j<=2;j++)
		{
			for(k=0;k<=2;k++)
			{
				for(l=0;l<=2;l++)
				{
					lt=j-k;
					if(lt<0)
						lt+=3;
					if(k==l)
					{
						f[i][j][k][1]=(f[i][j][k][1]+f[i-1][lt][l][0])%INF;
						f[i][j][k][1]=(f[i][j][k][1]+f[i-1][lt][l][1])%INF;
					}
					else
					{
						f[i][j][k][0]=(f[i][j][k][0]+f[i-1][lt][l][0])%INF;
						f[i][j][k][1]=(f[i][j][k][1]+f[i-1][lt][l][1])%INF;
					}
				}
			//	printf("%d %d %d %d %d %d\n",i,j,k,l,f[i][j][k][0],f[i][j][k][1]);
			}
		}
	}
	for(i=0;i<=2;i++)
	{
		ans=(ans+f[n][pp][i][1])%INF;
	}
	printf("%d\n",ans);
	return 0;
}

```