#include<bits/stdc++.h>
using namespace std;
typedef int sign;
typedef long long ll;
#define For(i,a,b) for(register sign i=(sign)(a);i<=(sign)(b);++i)
#define Fordown(i,a,b) for(register sign i=(sign)(a);i>=(sign)(b);--i)
const int N=2e5+5;
template<typename T>bool cmax(T &a,T b){return (a<b)?a=b,1:0;}
template<typename T>bool cmin(T &a,T b){return (a>b)?a=b,1:0;}
template<typename T>T read()
{
	T ans=0,f=1;
	char ch=getchar();
	while(!isdigit(ch)&&ch!='-')ch=getchar();
	if(ch=='-')f=-1,ch=getchar();
	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch-'0'),ch=getchar();
	return ans*f;
}
template<typename T>void write(T x,char y)
{
	if(x==0)
	{
		putchar('0'),putchar(y);
		return;
	}
	if(x<0)
	{
		putchar('-');
		x=-x;
	}
	static char wr[20];
	int top=0;
	for(;x;x/=10)wr[++top]=x%10+'0';
	while(top)putchar(wr[top--]);
	putchar(y);
}
void file()
{
#ifndef ONLINE_JUDGE
	freopen("F.in","r",stdin);
	freopen("F.out","w",stdout);
#endif
}
char s[N];
int n;
const int mo=998244353;
int dp[N][3][3][2];
void add(int &x,int y){x+=y;x-=(x>=mo?mo:0);}
void input()
{
	scanf("%s",s+1);
	n=strlen(s+1);
}
void check()
{
	int flag=1;
	For(i,2,n)if(s[i-1]!=s[i])flag=0;
	if(flag){puts("1");exit(0);}
	if(n<=3)
	{
		if(n==2)puts("2");
		else if(s[1]!=s[2]&&s[2]!=s[3]&&s[1]!=s[3])puts("3");
		else if(s[1]==s[3])puts("7");
		else puts("6");
		exit(0);
	}
}
void work()
{
	check();
	int d=0;
	For(i,1,n)d=(d+s[i]-'a')%3;
	For(i,0,2)dp[1][i][i][0]=1;
	int ans=1;
	For(i,2,n)if(s[i-1]==s[i])ans=0;
	For(i,2,n)For(j,0,2)For(a,0,2)For(l,0,1)if(dp[i-1][j][a][l])
	{
		For(b,0,2)add(dp[i][(j+b)%3][b][l|(a==b)],dp[i-1][j][a][l]);
	}
	add(ans,dp[n][d][0][1]);
	add(ans,dp[n][d][1][1]);
	add(ans,dp[n][d][2][1]);
	write(ans,'\n');
}
int main()
{

	input();
	work();
	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<bits/stdc++.h>
using namespace std;
typedef int sign;
typedef long long ll;
#define For(i,a,b) for(register sign i=(sign)(a);i<=(sign)(b);++i)
#define Fordown(i,a,b) for(register sign i=(sign)(a);i>=(sign)(b);--i)
const int N=2e5+5;
template<typename T>bool cmax(T &a,T b){return (a<b)?a=b,1:0;}
template<typename T>bool cmin(T &a,T b){return (a>b)?a=b,1:0;}
template<typename T>T read()
{
	T ans=0,f=1;
	char ch=getchar();
	while(!isdigit(ch)&&ch!='-')ch=getchar();
	if(ch=='-')f=-1,ch=getchar();
	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch-'0'),ch=getchar();
	return ans*f;
}
template<typename T>void write(T x,char y)
{
	if(x==0)
	{
		putchar('0'),putchar(y);
		return;
	}
	if(x<0)
	{
		putchar('-');
		x=-x;
	}
	static char wr[20];
	int top=0;
	for(;x;x/=10)wr[++top]=x%10+'0';
	while(top)putchar(wr[top--]);
	putchar(y);
}
void file()
{
#ifndef ONLINE_JUDGE
	freopen("F.in","r",stdin);
	freopen("F.out","w",stdout);
#endif
}
char s[N];
int n;
const int mo=998244353;
int dp[N][3][3][2];
void add(int &x,int y){x+=y;x-=(x>=mo?mo:0);}
void input()
{
	scanf("%s",s+1);
	n=strlen(s+1);
}
void check()
{
	int flag=1;
	For(i,2,n)if(s[i-1]!=s[i])flag=0;
	if(flag){puts("1");exit(0);}
	if(n<=3)
	{
		if(n==2)puts("2");
		else if(s[1]!=s[2]&&s[2]!=s[3]&&s[1]!=s[3])puts("3");
		else if(s[1]==s[3])puts("7");
		else puts("6");
		exit(0);
	}
}
void work()
{
	check();
	int d=0;
	For(i,1,n)d=(d+s[i]-'a')%3;
	For(i,0,2)dp[1][i][i][0]=1;
	int ans=1;
	For(i,2,n)if(s[i-1]==s[i])ans=0;
	For(i,2,n)For(j,0,2)For(a,0,2)For(l,0,1)if(dp[i-1][j][a][l])
	{
		For(b,0,2)add(dp[i][(j+b)%3][b][l|(a==b)],dp[i-1][j][a][l]);
	}
	add(ans,dp[n][d][0][1]);
	add(ans,dp[n][d][1][1]);
	add(ans,dp[n][d][2][1]);
	write(ans,'\n');
}
int main()
{

	input();
	work();
	return 0;
}


```