#include<bits/stdc++.h>
using namespace std;
int len;
long long  dp[200005][3][3][2];
char t[200005];
#define mo 998244353
int hashw(char c[]){
	int ans=0;
	for(int i=0;i<strlen(c);i++)
		ans=10*ans+c[i]-'a'+1;
	return ans;
}
bool vis[100000];
int wei(int t,int w){
	t=t/(pow(10,w-1));
	return t%10;
}
void doit(){
	int ans=1;
	queue<int> q;
	q.push(hashw(t));
	vis[hashw(t)]=1;
	while(!q.empty()){
		int s=q.front();q.pop();
		for(int i=2;i<=len;i++){
			int u=wei(s,i),v=wei(s,i-1),a1=6-u-v;
			if(u==v) continue;
			int k=s+( a1-wei(s,i) )*pow(10,i-1)+(a1-wei(s,i-1))*pow(10,i-2);
			if(!vis[k]){
				vis[k]=1;
				q.push(k);ans++;
			}
		}
	}
	cout<<ans;
}
int main()
{
	
	scanf("%s",t);
	len=strlen(t);
	int sum=0;
	for(int i=0;i<len;i++)
		sum+=t[i]-'a';
	sum%=3;
	
	bool h=1;
	for(int i=1;i<len;i++)
		 if(t[i]!=t[i-1]) h=0;
	if(h) {cout<<1;return 0;}
	
	if(len<=3) {doit();return 0;}
	for(int i=0;i<=2;i++)
		dp[1][i][i][0]=1;
	for(int i=2;i<=len;i++){
		for(int p=0;p<=2;p++)
		for(int j=0;j<=2;j++)
		for(int k=0;k<=2;k++){
			if(p==j)
				dp[i][p][(k+p)%3][1]+=dp[i-1][j][k][0];	
			else 
				dp[i][p][(k+p)%3][0]+=dp[i-1][j][k][0];
			dp[i][p][(k+p)%3][1]+=dp[i-1][j][k][1];
			dp[i][p][(k+p)%3][1]%=mo;
			dp[i][p][(k+p)%3][0]%=mo;
		}
	}
	long long ans=0;
	for(int i=0;i<=2;i++)
		ans+=dp[len][i][sum][1];
	int flag=1;
	for(int i=1;i<len;i++)
		if(t[i]==t[i-1]) flag=0;
	cout<<(ans+flag)%mo;
	
	return 0;
}
### Prompt

Create a solution in cpp for 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;
int len;
long long  dp[200005][3][3][2];
char t[200005];
#define mo 998244353
int hashw(char c[]){
	int ans=0;
	for(int i=0;i<strlen(c);i++)
		ans=10*ans+c[i]-'a'+1;
	return ans;
}
bool vis[100000];
int wei(int t,int w){
	t=t/(pow(10,w-1));
	return t%10;
}
void doit(){
	int ans=1;
	queue<int> q;
	q.push(hashw(t));
	vis[hashw(t)]=1;
	while(!q.empty()){
		int s=q.front();q.pop();
		for(int i=2;i<=len;i++){
			int u=wei(s,i),v=wei(s,i-1),a1=6-u-v;
			if(u==v) continue;
			int k=s+( a1-wei(s,i) )*pow(10,i-1)+(a1-wei(s,i-1))*pow(10,i-2);
			if(!vis[k]){
				vis[k]=1;
				q.push(k);ans++;
			}
		}
	}
	cout<<ans;
}
int main()
{
	
	scanf("%s",t);
	len=strlen(t);
	int sum=0;
	for(int i=0;i<len;i++)
		sum+=t[i]-'a';
	sum%=3;
	
	bool h=1;
	for(int i=1;i<len;i++)
		 if(t[i]!=t[i-1]) h=0;
	if(h) {cout<<1;return 0;}
	
	if(len<=3) {doit();return 0;}
	for(int i=0;i<=2;i++)
		dp[1][i][i][0]=1;
	for(int i=2;i<=len;i++){
		for(int p=0;p<=2;p++)
		for(int j=0;j<=2;j++)
		for(int k=0;k<=2;k++){
			if(p==j)
				dp[i][p][(k+p)%3][1]+=dp[i-1][j][k][0];	
			else 
				dp[i][p][(k+p)%3][0]+=dp[i-1][j][k][0];
			dp[i][p][(k+p)%3][1]+=dp[i-1][j][k][1];
			dp[i][p][(k+p)%3][1]%=mo;
			dp[i][p][(k+p)%3][0]%=mo;
		}
	}
	long long ans=0;
	for(int i=0;i<=2;i++)
		ans+=dp[len][i][sum][1];
	int flag=1;
	for(int i=1;i<len;i++)
		if(t[i]==t[i-1]) flag=0;
	cout<<(ans+flag)%mo;
	
	return 0;
}
```