#include<cstdio>
#include<cstring>
const long long MAXN=200005,MOD=998244353;

char S[MAXN];
long long dp[MAXN][3][3][2];

int main()
{
	scanf("%s",S+1);
	long long n=strlen(S+1),sum=0;
	if(n==2)
	{
		printf("%d\n",1+(S[1]!=S[2]));
		return 0;
	}
	if(n==3)
	{
		if(S[1]!=S[2]&&S[2]!=S[3]&&S[3]!=S[1])
			puts("3");
		else if((S[1]==S[2]&&S[2]!=S[3])||(S[2]==S[3]&&S[1]!=S[2]))
			puts("6");
		else if(S[1]==S[3]&&S[1]!=S[2])
			puts("7");
		else if(S[1]==S[2]&&S[2]==S[3])
			puts("1");
		return 0;
	}
	bool flag=false,flag2=true;
	for(long long i=1;i<=n;i++)
	{
		sum=(sum+S[i]-'a')%3;
		if(S[i]==S[i+1])
			flag=true;
		if(S[i]!=S[1])
			flag2=false;
	}
	if(flag2)
	{
		puts("1");
		return 0;
	}
	dp[1][0][0][0]=1;
	dp[1][1][1][0]=1;
	dp[1][2][2][0]=1;
	for(long long i=2;i<=n;i++)
		for(long long j=0;j<3;j++)
			for(long long k=0;k<3;k++)
			{
				for(long long p=0;p<3;p++)
					if(p!=k)
						dp[i][j][k][0]=(dp[i][j][k][0]+dp[i-1][(j-k+3)%3][p][0])%MOD;
				for(long long p=0;p<3;p++)
				{
					dp[i][j][k][1]=(dp[i][j][k][1]+dp[i-1][(j-k+3)%3][p][1])%MOD;
					if(p==k)
						dp[i][j][k][1]=(dp[i][j][k][1]+dp[i-1][(j-k+3)%3][p][0])%MOD;
				}
				//printf("dp[%d][%d][%d][%d]=%d\n",i,j,k,0,dp[i][j][k][0]);
				//printf("dp[%d][%d][%d][%d]=%d\n",i,j,k,1,dp[i][j][k][1]);
			}
	long long ans=0;
	for(long long j=0;j<3;j++)
		ans=(ans+dp[n][sum][j][1])%MOD;
	ans+=(!flag);
	printf("%lld\n",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<cstdio>
#include<cstring>
const long long MAXN=200005,MOD=998244353;

char S[MAXN];
long long dp[MAXN][3][3][2];

int main()
{
	scanf("%s",S+1);
	long long n=strlen(S+1),sum=0;
	if(n==2)
	{
		printf("%d\n",1+(S[1]!=S[2]));
		return 0;
	}
	if(n==3)
	{
		if(S[1]!=S[2]&&S[2]!=S[3]&&S[3]!=S[1])
			puts("3");
		else if((S[1]==S[2]&&S[2]!=S[3])||(S[2]==S[3]&&S[1]!=S[2]))
			puts("6");
		else if(S[1]==S[3]&&S[1]!=S[2])
			puts("7");
		else if(S[1]==S[2]&&S[2]==S[3])
			puts("1");
		return 0;
	}
	bool flag=false,flag2=true;
	for(long long i=1;i<=n;i++)
	{
		sum=(sum+S[i]-'a')%3;
		if(S[i]==S[i+1])
			flag=true;
		if(S[i]!=S[1])
			flag2=false;
	}
	if(flag2)
	{
		puts("1");
		return 0;
	}
	dp[1][0][0][0]=1;
	dp[1][1][1][0]=1;
	dp[1][2][2][0]=1;
	for(long long i=2;i<=n;i++)
		for(long long j=0;j<3;j++)
			for(long long k=0;k<3;k++)
			{
				for(long long p=0;p<3;p++)
					if(p!=k)
						dp[i][j][k][0]=(dp[i][j][k][0]+dp[i-1][(j-k+3)%3][p][0])%MOD;
				for(long long p=0;p<3;p++)
				{
					dp[i][j][k][1]=(dp[i][j][k][1]+dp[i-1][(j-k+3)%3][p][1])%MOD;
					if(p==k)
						dp[i][j][k][1]=(dp[i][j][k][1]+dp[i-1][(j-k+3)%3][p][0])%MOD;
				}
				//printf("dp[%d][%d][%d][%d]=%d\n",i,j,k,0,dp[i][j][k][0]);
				//printf("dp[%d][%d][%d][%d]=%d\n",i,j,k,1,dp[i][j][k][1]);
			}
	long long ans=0;
	for(long long j=0;j<3;j++)
		ans=(ans+dp[n][sum][j][1])%MOD;
	ans+=(!flag);
	printf("%lld\n",ans);
	return 0;
}

```