#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#define cmin(a,b) (a>(b)?a=(b),1:0)
#define cmax(a,b) (a<(b)?a=(b),1:0)
#define dmin(a,b) ((a)<(b)?(a):(b))
#define dmax(a,b) ((a)>(b)?(a):(b))
namespace io
{
	int F()
	{
		int n=0,F=1;
		char ch;
		while((ch=getchar())!='-'&&(ch<'0'||ch>'9'));
		ch=='-'?F=0:n=ch-'0';
		while((ch=getchar())>='0'&&ch<='9')n=n*10+ch-'0';
		return F?n:-n;
	}
}
const int M=998244353;
int f[222222][3][4][2];
char s[222222],t[222222];
int main()
{
	scanf("%s",s+1);
	int n=strlen(s+1),sum=0;
	for(register int i=1;i<=n;++i)sum+=s[i]-'a';
	strcpy(t+1,s+1);
	std::sort(t+1,t+n+1);
	if(t[1]==t[n])puts("1"),exit(0);
	if(n==2)puts("2"),exit(0);
	if(n==3)
	{
		if(s[1]!=s[2]&&s[1]!=s[3]&&s[2]!=s[3])puts("3"),exit(0);
		if(s[1]==s[2]||s[2]==s[3])puts("6");
		if(s[1]==s[3])puts("7");
		exit(0);
	}
	f[0][0][3][0]=1;
	for(register int i=0;i<n;++i)
		for(register int j=0;j<=2;++j)
			for(register int la=0;la<=3;++la)
				for(register int k=0;k<=1;++k)
					for(register int d=0;d<=2;++d)
						(f[i+1][(j+d)%3][d][k|(la==d)]+=f[i][j][la][k])%=M;
	int ans=0;
	int fl=0;
	for(register int i=1;i<n;++i)if(s[i]==s[i+1])fl=1;
	if(fl==0)ans=1;
	for(register int la=0;la<=2;++la)(ans+=f[n][sum%3][la][1])%=M;
	printf("%d\n",ans);
	return 0;
}
### Prompt

In cpp, your task is to solve 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<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#define cmin(a,b) (a>(b)?a=(b),1:0)
#define cmax(a,b) (a<(b)?a=(b),1:0)
#define dmin(a,b) ((a)<(b)?(a):(b))
#define dmax(a,b) ((a)>(b)?(a):(b))
namespace io
{
	int F()
	{
		int n=0,F=1;
		char ch;
		while((ch=getchar())!='-'&&(ch<'0'||ch>'9'));
		ch=='-'?F=0:n=ch-'0';
		while((ch=getchar())>='0'&&ch<='9')n=n*10+ch-'0';
		return F?n:-n;
	}
}
const int M=998244353;
int f[222222][3][4][2];
char s[222222],t[222222];
int main()
{
	scanf("%s",s+1);
	int n=strlen(s+1),sum=0;
	for(register int i=1;i<=n;++i)sum+=s[i]-'a';
	strcpy(t+1,s+1);
	std::sort(t+1,t+n+1);
	if(t[1]==t[n])puts("1"),exit(0);
	if(n==2)puts("2"),exit(0);
	if(n==3)
	{
		if(s[1]!=s[2]&&s[1]!=s[3]&&s[2]!=s[3])puts("3"),exit(0);
		if(s[1]==s[2]||s[2]==s[3])puts("6");
		if(s[1]==s[3])puts("7");
		exit(0);
	}
	f[0][0][3][0]=1;
	for(register int i=0;i<n;++i)
		for(register int j=0;j<=2;++j)
			for(register int la=0;la<=3;++la)
				for(register int k=0;k<=1;++k)
					for(register int d=0;d<=2;++d)
						(f[i+1][(j+d)%3][d][k|(la==d)]+=f[i][j][la][k])%=M;
	int ans=0;
	int fl=0;
	for(register int i=1;i<n;++i)if(s[i]==s[i+1])fl=1;
	if(fl==0)ans=1;
	for(register int la=0;la<=2;++la)(ans+=f[n][sum%3][la][1])%=M;
	printf("%d\n",ans);
	return 0;
}
```