#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <set>
#define SIZE 200005
#define MOD 998244353

using namespace std;
typedef long long int ll;
typedef pair <int,int> P;

void chadd(int &X,int Y)
{
	X+=Y;
	if(X>=MOD) X-=MOD;
}
char str[SIZE];
int dp[2][3][3][3][2];

int main()
{
	scanf("%s",&str);
	int n=strlen(str);
	bool up=true;
	for(int i=0;i<n;i++)
	{
		if(str[i]!=str[0]) up=false;
	}
	if(up)
	{
		puts("1");
		return 0;
	}
	if(n==2)
	{
		puts("2");
		return 0;
	}
	if(n==3&&str[0]!=str[1]&&str[1]!=str[2]&&str[0]!=str[2])
	{
		puts("3");
		return 0;
	}
	int pos=0;
	dp[pos][2][2][0][0]=1;
	dp[pos][1][0][1][0]=1;
	dp[pos][0][1][2][0]=1;
	for(int i=1;i<n;i++)
	{
		pos^=1;
		memset(dp[pos],0,sizeof(dp[pos]));
		for(int a=0;a<3;a++)
		{
			for(int b=0;b<3;b++)
			{
				for(int c=0;c<3;c++)
				{
					for(int t=0;t<3;t++)//nxt
					{
						int na=a,nb=b;
						if(t==0)
						{
							na+=2,nb+=2;
							if(na>=3) na-=3;
							if(nb>=3) nb-=3;
						}
						else if(t==1)
						{
							na++;
							if(na>=3) na-=3;
						}
						else
						{
							nb++;
							if(nb>=3) nb-=3;
						}
						if(c==t)
						{
							chadd(dp[pos][na][nb][t][1],dp[pos^1][a][b][c][0]);
							chadd(dp[pos][na][nb][t][1],dp[pos^1][a][b][c][1]);
						}
						else
						{
							chadd(dp[pos][na][nb][t][0],dp[pos^1][a][b][c][0]);
							chadd(dp[pos][na][nb][t][1],dp[pos^1][a][b][c][1]);
						}
					}
				}
			}
		}
	}
	int b=0,c=0;
	up=true;
	for(int i=0;i<n;i++)
	{
		if(str[i]=='a')
		{
			b+=2,c+=2;
			b%=3,c%=3;
		}
		else if(str[i]=='b')
		{
			b++;
			b%=3;
		}
		else
		{
			c++;
			c%=3;
		}
		if(i>0&&str[i]==str[i-1])
		{
			up=false;
		}
	}
	int ret=up;
	for(int t=0;t<3;t++) chadd(ret,dp[pos][b][c][t][1]);
	printf("%d\n",ret);
	return 0;
}

### Prompt

Please provide a cpp coded solution 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 <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <set>
#define SIZE 200005
#define MOD 998244353

using namespace std;
typedef long long int ll;
typedef pair <int,int> P;

void chadd(int &X,int Y)
{
	X+=Y;
	if(X>=MOD) X-=MOD;
}
char str[SIZE];
int dp[2][3][3][3][2];

int main()
{
	scanf("%s",&str);
	int n=strlen(str);
	bool up=true;
	for(int i=0;i<n;i++)
	{
		if(str[i]!=str[0]) up=false;
	}
	if(up)
	{
		puts("1");
		return 0;
	}
	if(n==2)
	{
		puts("2");
		return 0;
	}
	if(n==3&&str[0]!=str[1]&&str[1]!=str[2]&&str[0]!=str[2])
	{
		puts("3");
		return 0;
	}
	int pos=0;
	dp[pos][2][2][0][0]=1;
	dp[pos][1][0][1][0]=1;
	dp[pos][0][1][2][0]=1;
	for(int i=1;i<n;i++)
	{
		pos^=1;
		memset(dp[pos],0,sizeof(dp[pos]));
		for(int a=0;a<3;a++)
		{
			for(int b=0;b<3;b++)
			{
				for(int c=0;c<3;c++)
				{
					for(int t=0;t<3;t++)//nxt
					{
						int na=a,nb=b;
						if(t==0)
						{
							na+=2,nb+=2;
							if(na>=3) na-=3;
							if(nb>=3) nb-=3;
						}
						else if(t==1)
						{
							na++;
							if(na>=3) na-=3;
						}
						else
						{
							nb++;
							if(nb>=3) nb-=3;
						}
						if(c==t)
						{
							chadd(dp[pos][na][nb][t][1],dp[pos^1][a][b][c][0]);
							chadd(dp[pos][na][nb][t][1],dp[pos^1][a][b][c][1]);
						}
						else
						{
							chadd(dp[pos][na][nb][t][0],dp[pos^1][a][b][c][0]);
							chadd(dp[pos][na][nb][t][1],dp[pos^1][a][b][c][1]);
						}
					}
				}
			}
		}
	}
	int b=0,c=0;
	up=true;
	for(int i=0;i<n;i++)
	{
		if(str[i]=='a')
		{
			b+=2,c+=2;
			b%=3,c%=3;
		}
		else if(str[i]=='b')
		{
			b++;
			b%=3;
		}
		else
		{
			c++;
			c%=3;
		}
		if(i>0&&str[i]==str[i-1])
		{
			up=false;
		}
	}
	int ret=up;
	for(int t=0;t<3;t++) chadd(ret,dp[pos][b][c][t][1]);
	printf("%d\n",ret);
	return 0;
}

```