#include <iostream>
#include <algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<iomanip>
#define sqr(x) (x)*(x)
using namespace std;
long long n,m,i,j,k,l,dp[200005][3][3][2],sum,cnt,cnt2,mod=998244353,ans;
string st;
int main()
{
	ios_base::sync_with_stdio(0); 
	cin>>st;
	if (st.length()==2)
	{
		if (st[0]==st[1]) cout<<1; else cout<<2;
		return 0;
	}
	if (st.length()==3)
	{
		if (st[0]!=st[1]&&st[1]!=st[2]&&st[0]!=st[2]) cout<<3;
		else if (st[0]==st[1]&&st[1]==st[2]) cout<<1;
		else if (st[0]!=st[2]) cout<<6;
		else cout<<7;
		return 0; 
	}
	for (i=0;i<st.length();i++)
	{
		sum+=st[i]-'a';
		if (i&&st[i-1]!=st[i]) cnt++;
		if (i&&st[i-1]==st[i]) cnt2++;
	}
	if (cnt==0)
	{
		cout<<1;
		return 0;
	}
	dp[1][0][0][0]=1;
	dp[1][1][1][0]=1;
	dp[1][2][2][0]=1;
	n=st.length();
	for (i=2;i<=n;i++)
	{
		for (j=0;j<3;j++)
		{
			for (k=0;k<3;k++)
			{
				for (l=0;l<3;l++)
				{
					if (l!=k)
					{
						(dp[i][(j+l)%3][l][0]+=dp[i-1][j][k][0])%=mod;
						(dp[i][(j+l)%3][l][1]+=dp[i-1][j][k][1])%=mod;
					}
					else
					{
						(dp[i][(j+l)%3][l][1]+=dp[i-1][j][k][0]+dp[i-1][j][k][1])%=mod;
					}
				}
			}
		}
	}
	if (!cnt2) ans=1; else ans=0;
	for (i=0;i<3;i++) (ans+=dp[n][sum%3][i][1])%=mod;
	cout<<ans;
	return 0;
}
### Prompt

Please create a solution in cpp 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 <iostream>
#include <algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<iomanip>
#define sqr(x) (x)*(x)
using namespace std;
long long n,m,i,j,k,l,dp[200005][3][3][2],sum,cnt,cnt2,mod=998244353,ans;
string st;
int main()
{
	ios_base::sync_with_stdio(0); 
	cin>>st;
	if (st.length()==2)
	{
		if (st[0]==st[1]) cout<<1; else cout<<2;
		return 0;
	}
	if (st.length()==3)
	{
		if (st[0]!=st[1]&&st[1]!=st[2]&&st[0]!=st[2]) cout<<3;
		else if (st[0]==st[1]&&st[1]==st[2]) cout<<1;
		else if (st[0]!=st[2]) cout<<6;
		else cout<<7;
		return 0; 
	}
	for (i=0;i<st.length();i++)
	{
		sum+=st[i]-'a';
		if (i&&st[i-1]!=st[i]) cnt++;
		if (i&&st[i-1]==st[i]) cnt2++;
	}
	if (cnt==0)
	{
		cout<<1;
		return 0;
	}
	dp[1][0][0][0]=1;
	dp[1][1][1][0]=1;
	dp[1][2][2][0]=1;
	n=st.length();
	for (i=2;i<=n;i++)
	{
		for (j=0;j<3;j++)
		{
			for (k=0;k<3;k++)
			{
				for (l=0;l<3;l++)
				{
					if (l!=k)
					{
						(dp[i][(j+l)%3][l][0]+=dp[i-1][j][k][0])%=mod;
						(dp[i][(j+l)%3][l][1]+=dp[i-1][j][k][1])%=mod;
					}
					else
					{
						(dp[i][(j+l)%3][l][1]+=dp[i-1][j][k][0]+dp[i-1][j][k][1])%=mod;
					}
				}
			}
		}
	}
	if (!cnt2) ans=1; else ans=0;
	for (i=0;i<3;i++) (ans+=dp[n][sum%3][i][1])%=mod;
	cout<<ans;
	return 0;
}
```