#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
char s[200010];
bool v[3][3][3];
const int mod=998244353;
int f[200010][3][3][2],n,mo,p,ans,tot=1,q1[100],q2[100],q3[100];
bool vis[200010][3][3][2]; 
int dp(int len,int sum,int pre,int tag)
{
	if (len>n) return (sum==mo&&tag);
	if (vis[len][sum][pre][tag]) return f[len][sum][pre][tag];
	vis[len][sum][pre][tag]=1;
	int S=0;
	for (int i=0;i<3;i++)
	{
		S+=dp(len+1,(sum+i)%3,i,tag|(i==pre));
		if (S>=mod) S-=mod;
	}
	return f[len][sum][pre][tag]=S;
}
int main()
{
	scanf("%s",s+1);n=strlen(s+1);p=1;
	for (int i=1;i<=n;i++) {if (s[i]==s[i-1]) p=0;else tot--;mo+=s[i]-'a';}
	if (tot==0) {printf("1");return 0;}
	if (n==2) {printf("2");return 0;}
	if (n==3)
	{
		int h=0,t=0;
		q1[++t]=s[1]-'a';q2[t]=s[2]-'a';q3[t]=s[3]-'a';
		v[q1[t]][q2[t]][q3[t]]=1;
		int n1=0,n2=0,n3=0;
		while (h<t)
		{
			h++;
			if (q1[h]!=q2[h])
				for (int i=0;i<=2;i++) if (i!=q1[h]&&i!=q2[h])
				{
					n1=i,n2=i,n3=q3[h];
					if (!v[n1][n2][n3]) v[n1][n2][n3]=1,q1[++t]=n1,q2[t]=n2,q3[t]=n3;
				}
			if (q3[h]!=q2[h])
				for (int i=0;i<=2;i++) if (i!=q3[h]&&i!=q2[h])
				{
					n3=i,n2=i,n1=q1[h];
					if (!v[n1][n2][n3]) v[n1][n2][n3]=1,q1[++t]=n1,q2[t]=n2,q3[t]=n3;
				}
		}
		printf("%d",t);
		return 0;
	}
	mo%=3;
	for (int i=0;i<3;i++){ans+=dp(2,i,i,0);if (ans>=mod) ans-=mod;}
	ans+=p;
	printf("%d",ans);
} 
### Prompt

Construct a Cpp code solution to the problem outlined:

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<iostream>
#include<cstring>
using namespace std;
char s[200010];
bool v[3][3][3];
const int mod=998244353;
int f[200010][3][3][2],n,mo,p,ans,tot=1,q1[100],q2[100],q3[100];
bool vis[200010][3][3][2]; 
int dp(int len,int sum,int pre,int tag)
{
	if (len>n) return (sum==mo&&tag);
	if (vis[len][sum][pre][tag]) return f[len][sum][pre][tag];
	vis[len][sum][pre][tag]=1;
	int S=0;
	for (int i=0;i<3;i++)
	{
		S+=dp(len+1,(sum+i)%3,i,tag|(i==pre));
		if (S>=mod) S-=mod;
	}
	return f[len][sum][pre][tag]=S;
}
int main()
{
	scanf("%s",s+1);n=strlen(s+1);p=1;
	for (int i=1;i<=n;i++) {if (s[i]==s[i-1]) p=0;else tot--;mo+=s[i]-'a';}
	if (tot==0) {printf("1");return 0;}
	if (n==2) {printf("2");return 0;}
	if (n==3)
	{
		int h=0,t=0;
		q1[++t]=s[1]-'a';q2[t]=s[2]-'a';q3[t]=s[3]-'a';
		v[q1[t]][q2[t]][q3[t]]=1;
		int n1=0,n2=0,n3=0;
		while (h<t)
		{
			h++;
			if (q1[h]!=q2[h])
				for (int i=0;i<=2;i++) if (i!=q1[h]&&i!=q2[h])
				{
					n1=i,n2=i,n3=q3[h];
					if (!v[n1][n2][n3]) v[n1][n2][n3]=1,q1[++t]=n1,q2[t]=n2,q3[t]=n3;
				}
			if (q3[h]!=q2[h])
				for (int i=0;i<=2;i++) if (i!=q3[h]&&i!=q2[h])
				{
					n3=i,n2=i,n1=q1[h];
					if (!v[n1][n2][n3]) v[n1][n2][n3]=1,q1[++t]=n1,q2[t]=n2,q3[t]=n3;
				}
		}
		printf("%d",t);
		return 0;
	}
	mo%=3;
	for (int i=0;i<3;i++){ans+=dp(2,i,i,0);if (ans>=mod) ans-=mod;}
	ans+=p;
	printf("%d",ans);
} 
```