#include<iostream>
#include<cstdio>
#include<cstring>

typedef long long ll;
const int N=201000,MOD=998244353;
ll qpow(ll a,ll b){ll c=1;for(;b;b>>=1,a=a*a%MOD)if(b&1)c=c*a%MOD;return c;}
void inc(int a,int &b){b=(a+b)%MOD;}

int s[N];
int n;

namespace bf
{
	bool vis[N];
	int ans;
	void dfs(int state)
	{
		if(vis[state])return;
		vis[state]=1,ans++;

		int t[4],dt[4];
		for(int i=n;i;i--)t[i]=state%3,state/=3;

		for(int i=1;i<n;i++)
			if(t[i]!=t[i+1])
			{
				for(int j=1;j<=n;j++)dt[j]=t[j];
				int tmp=((t[i]+1)^(t[i+1]+1))-1,dk=0;
				dt[i]=dt[i+1]=tmp;
				for(int i=1;i<=n;i++)
					dk=dk*3+dt[i];
				dfs(dk);
			}
	}
	void solve()
	{
		int k=0;
		for(int i=1;i<=n;i++)k=k*3+s[i];
		ans=0,dfs(k);
		printf("%d\n",ans);
	}
}
namespace qwq
{
	int f[N][3][3];

	bool spj()
	{
		for(int i=1;i<n;i++)
			if(s[i]==s[i+1])return 0;
		return 1;
	}
	bool equal()
	{
		for(int i=1;i<n;i++)
			if(s[i]!=s[i+1])return 0;
		return 1;
	}

	void solve()
	{
		if(equal()){printf("1\n");return;}

		int tmp=0;
		for(int i=1;i<=n;i++)tmp=(tmp+s[i])%3;

		for(int i=0;i<3;i++)f[1][i][i]=1;
		for(int i=1;i<n;i++)
			for(int j=0;j<3;j++)
				for(int k=0;k<3;k++)
					for(int l=0;l<3;l++)
						if(l!=j)inc(f[i][j][k],f[i+1][l][(k+l)%3]);

		int ans=qpow(3,n-1);

		for(int i=0;i<3;i++)
			ans=(ans-f[n][i][tmp])%MOD;
		ans=(ans+spj()+MOD)%MOD;

		printf("%d\n",ans);
	}
}

char tmp[N];
int main()
{
	scanf("%s",tmp+1);
	n=strlen(tmp+1);
	for(int i=1;i<=n;i++)
		s[i]=tmp[i]-'a';
	if(n<=3)bf::solve();
	else qwq::solve();

	return 0;
}

### Prompt

Generate 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<iostream>
#include<cstdio>
#include<cstring>

typedef long long ll;
const int N=201000,MOD=998244353;
ll qpow(ll a,ll b){ll c=1;for(;b;b>>=1,a=a*a%MOD)if(b&1)c=c*a%MOD;return c;}
void inc(int a,int &b){b=(a+b)%MOD;}

int s[N];
int n;

namespace bf
{
	bool vis[N];
	int ans;
	void dfs(int state)
	{
		if(vis[state])return;
		vis[state]=1,ans++;

		int t[4],dt[4];
		for(int i=n;i;i--)t[i]=state%3,state/=3;

		for(int i=1;i<n;i++)
			if(t[i]!=t[i+1])
			{
				for(int j=1;j<=n;j++)dt[j]=t[j];
				int tmp=((t[i]+1)^(t[i+1]+1))-1,dk=0;
				dt[i]=dt[i+1]=tmp;
				for(int i=1;i<=n;i++)
					dk=dk*3+dt[i];
				dfs(dk);
			}
	}
	void solve()
	{
		int k=0;
		for(int i=1;i<=n;i++)k=k*3+s[i];
		ans=0,dfs(k);
		printf("%d\n",ans);
	}
}
namespace qwq
{
	int f[N][3][3];

	bool spj()
	{
		for(int i=1;i<n;i++)
			if(s[i]==s[i+1])return 0;
		return 1;
	}
	bool equal()
	{
		for(int i=1;i<n;i++)
			if(s[i]!=s[i+1])return 0;
		return 1;
	}

	void solve()
	{
		if(equal()){printf("1\n");return;}

		int tmp=0;
		for(int i=1;i<=n;i++)tmp=(tmp+s[i])%3;

		for(int i=0;i<3;i++)f[1][i][i]=1;
		for(int i=1;i<n;i++)
			for(int j=0;j<3;j++)
				for(int k=0;k<3;k++)
					for(int l=0;l<3;l++)
						if(l!=j)inc(f[i][j][k],f[i+1][l][(k+l)%3]);

		int ans=qpow(3,n-1);

		for(int i=0;i<3;i++)
			ans=(ans-f[n][i][tmp])%MOD;
		ans=(ans+spj()+MOD)%MOD;

		printf("%d\n",ans);
	}
}

char tmp[N];
int main()
{
	scanf("%s",tmp+1);
	n=strlen(tmp+1);
	for(int i=1;i<=n;i++)
		s[i]=tmp[i]-'a';
	if(n<=3)bf::solve();
	else qwq::solve();

	return 0;
}

```