#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define maxn 200005
using namespace std;
typedef long long ll;
const ll mod=998244353;
int n,val;
char s[maxn];
ll dp[maxn][5][5][5];
int check()
{
	int flag=false;
	for(int i=1;i<=n;i++)
	{
		val=(val+s[i]-'a')%3;
		if(s[i]!=s[1])
			flag=true;
	}
	return flag;
}
int main()
{
	scanf("%s",s+1); n=strlen(s+1);
	if(!check())
		return printf("1\n"),0;
	if(n==2)
		return printf("2\n"),0;
	if(n==3)
		return ((s[1]!=s[2] && s[1]!=s[3] && s[2]!=s[3])?printf("3\n"):(s[1]==s[3] ? printf("7\n") : printf("6\n"))),0;
 
	dp[0][0][0][3]=1;
 
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<3;j++)
		{
			for(int k=0;k<=1;k++)
			{
				for(int now=0;now<=3;now++)
				if(dp[i][j][k][now])
				{
					for(int nex=0;nex<=2;nex++)
					{
						ll &temp=dp[i+1][(j+nex)%3][k|(now==nex)][nex];
						temp=temp+dp[i][j][k][now];
						if(temp>=mod)
							temp-=mod;
					}
				}
			}
		}
	}
 
	ll ans=1;
	for(int i=0;i<3;i++)
	{
		ans+=dp[n][val][1][i];
		if(ans>=mod)
			ans-=mod;
	}
	for(int i=1;i<n;i++)
		if(s[i]==s[i+1])
		{
			ans--;
			break;
		}
 
	printf("%lld\n",(ans%mod+mod)%mod);
 
}
### Prompt

Develop a solution in CPP 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<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define maxn 200005
using namespace std;
typedef long long ll;
const ll mod=998244353;
int n,val;
char s[maxn];
ll dp[maxn][5][5][5];
int check()
{
	int flag=false;
	for(int i=1;i<=n;i++)
	{
		val=(val+s[i]-'a')%3;
		if(s[i]!=s[1])
			flag=true;
	}
	return flag;
}
int main()
{
	scanf("%s",s+1); n=strlen(s+1);
	if(!check())
		return printf("1\n"),0;
	if(n==2)
		return printf("2\n"),0;
	if(n==3)
		return ((s[1]!=s[2] && s[1]!=s[3] && s[2]!=s[3])?printf("3\n"):(s[1]==s[3] ? printf("7\n") : printf("6\n"))),0;
 
	dp[0][0][0][3]=1;
 
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<3;j++)
		{
			for(int k=0;k<=1;k++)
			{
				for(int now=0;now<=3;now++)
				if(dp[i][j][k][now])
				{
					for(int nex=0;nex<=2;nex++)
					{
						ll &temp=dp[i+1][(j+nex)%3][k|(now==nex)][nex];
						temp=temp+dp[i][j][k][now];
						if(temp>=mod)
							temp-=mod;
					}
				}
			}
		}
	}
 
	ll ans=1;
	for(int i=0;i<3;i++)
	{
		ans+=dp[n][val][1][i];
		if(ans>=mod)
			ans-=mod;
	}
	for(int i=1;i<n;i++)
		if(s[i]==s[i+1])
		{
			ans--;
			break;
		}
 
	printf("%lld\n",(ans%mod+mod)%mod);
 
}
```