#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=998244353;
#define inf 0x3f3f3f3f
string s;

ll dp[2000050][3][3];
ll qpow(ll n,ll k)
{
	ll ans=1;
	while(k)
	{
		if(k&1)
		ans=ans*n%mod;
		n=n*n%mod;
		k>>=1;
	}
	return ans;
}
int main()
{
	cin>>s;
	int len=s.size();
	if(len==1)
	{
		cout<<1<<endl;
		return 0;
	}
	else if(len==3)
	{

	 if(s[0]!=s[1]&&s[1]!=s[2]&&s[0]!=s[2])
	 {
	 	cout<<3;
	 	return 0;
	 }
	}
	bool flag=1;
	for(int i=0;i<len-1;i++)
	{
		if(s[i]!=s[i+1])
		{
			flag=0;
			break;
		}
	}
	if(flag)
	{
		cout<<1;
		return 0;
	}
	for(int i=0;i<3;i++)
	dp[1][i][i]=1;
	for(int i=1;i<len;i++)
	{
		for(int j=0;j<3;j++)
		{
			for(int k=0;k<3;k++)
			{
				for(int l=0;l<3;l++)
				{
					if(k==l)continue;
					int ss=j+l;
					ss%=3;
					dp[i+1][l][ss]+=dp[i][k][j];
					dp[i+1][l][ss]%=mod;
				}
			}

		}
	}
	ll ans=qpow(3,len-1);
	int tmp=0;
	flag=1;
	for(int i=0;i<len;i++)
	{
		tmp+=s[i]-'a';
		if(i)
		{
			flag&=(s[i]!=s[i-1]);
		}
	 } 
	 if(flag)
	 ans++;
	 tmp%=3;
	 for(int i=0;i<3;i++)
	 {
	 	ans-=dp[len][i][tmp];
	 	while(ans<0)
	 	ans+=mod;
	 }
	 cout<<ans%mod<<endl;
	return 0;
}
### 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<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=998244353;
#define inf 0x3f3f3f3f
string s;

ll dp[2000050][3][3];
ll qpow(ll n,ll k)
{
	ll ans=1;
	while(k)
	{
		if(k&1)
		ans=ans*n%mod;
		n=n*n%mod;
		k>>=1;
	}
	return ans;
}
int main()
{
	cin>>s;
	int len=s.size();
	if(len==1)
	{
		cout<<1<<endl;
		return 0;
	}
	else if(len==3)
	{

	 if(s[0]!=s[1]&&s[1]!=s[2]&&s[0]!=s[2])
	 {
	 	cout<<3;
	 	return 0;
	 }
	}
	bool flag=1;
	for(int i=0;i<len-1;i++)
	{
		if(s[i]!=s[i+1])
		{
			flag=0;
			break;
		}
	}
	if(flag)
	{
		cout<<1;
		return 0;
	}
	for(int i=0;i<3;i++)
	dp[1][i][i]=1;
	for(int i=1;i<len;i++)
	{
		for(int j=0;j<3;j++)
		{
			for(int k=0;k<3;k++)
			{
				for(int l=0;l<3;l++)
				{
					if(k==l)continue;
					int ss=j+l;
					ss%=3;
					dp[i+1][l][ss]+=dp[i][k][j];
					dp[i+1][l][ss]%=mod;
				}
			}

		}
	}
	ll ans=qpow(3,len-1);
	int tmp=0;
	flag=1;
	for(int i=0;i<len;i++)
	{
		tmp+=s[i]-'a';
		if(i)
		{
			flag&=(s[i]!=s[i-1]);
		}
	 } 
	 if(flag)
	 ans++;
	 tmp%=3;
	 for(int i=0;i<3;i++)
	 {
	 	ans-=dp[len][i][tmp];
	 	while(ans<0)
	 	ans+=mod;
	 }
	 cout<<ans%mod<<endl;
	return 0;
}
```