#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define SF scanf
#define PF printf
#define MAXN 200010
#define MOD 998244353
using namespace std;
typedef long long ll;
char s[MAXN];
int vis[50],len;
ll dp[MAXN][2][3][3];
int get_num(char s[]){
	int res=0;
	for(int i=0;i<len;i++)
		res=res*3+(s[i]-'a');
	return res;
}
void dfs(char s[]){
	int num=get_num(s);
	if(vis[num]==1)
		return ;
	vis[num]=1;
	char s1,s2,s3;
	for(int i=1;i<len;i++){
		if(s[i]!=s[i-1]){
			s1=s[i],s2=s[i-1];
			s3=((s1-'a'+s2-'a')*2)%3+'a';
			s[i]=s[i-1]=s3;
			dfs(s);
			s[i]=s1;
			s[i-1]=s2;
		}
	}
}
int main(){
	SF("%s",s);
	len=strlen(s);
	bool flag=0;
	for(int i=1;i<len;i++){
		if(s[i]!=s[i-1])
			flag=1;
	}
	if(flag==0){
		PF("1");
		return 0;
	}
	if(len<=3){
		dfs(s);
		int sum=0;
		for(int i=0;i<27;i++)
			if(vis[i]==1)
				sum++;
		PF("%d\n",sum);
		return 0;
	}
	int sum=0;
	for(int i=0;i<len;i++){
		sum+=s[i]-'a';
		sum%=3;
	}
	dp[0][0][0][0]=1;
	for(int i=0;i<len;i++)
		for(int tag=0;tag<2;tag++)
			for(int sum1=0;sum1<3;sum1++)
				for(int las=0;las<3;las++)
					for(int now=0;now<3;now++){
						if(now==las&&i!=0){
							dp[i+1][1][(sum1+now)%3][now]+=dp[i][tag][sum1][las];
							dp[i+1][1][(sum1+now)%3][now]%=MOD;
						}
						else{
							dp[i+1][tag][(sum1+now)%3][now]+=dp[i][tag][sum1][las];
							dp[i+1][tag][(sum1+now)%3][now]%=MOD;
						}
					}
	ll ans=0;
	for(int i=0;i<3;i++)
		ans=(ans+dp[len][1][sum][i])%MOD;
	flag=0;
	for(int i=1;i<len;i++)
		if(s[i]==s[i-1])
			flag=1;
	if(flag==0)
		ans=(ans+1ll)%MOD;
	PF("%lld",ans);
} 
### Prompt

Your task is to create 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<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define SF scanf
#define PF printf
#define MAXN 200010
#define MOD 998244353
using namespace std;
typedef long long ll;
char s[MAXN];
int vis[50],len;
ll dp[MAXN][2][3][3];
int get_num(char s[]){
	int res=0;
	for(int i=0;i<len;i++)
		res=res*3+(s[i]-'a');
	return res;
}
void dfs(char s[]){
	int num=get_num(s);
	if(vis[num]==1)
		return ;
	vis[num]=1;
	char s1,s2,s3;
	for(int i=1;i<len;i++){
		if(s[i]!=s[i-1]){
			s1=s[i],s2=s[i-1];
			s3=((s1-'a'+s2-'a')*2)%3+'a';
			s[i]=s[i-1]=s3;
			dfs(s);
			s[i]=s1;
			s[i-1]=s2;
		}
	}
}
int main(){
	SF("%s",s);
	len=strlen(s);
	bool flag=0;
	for(int i=1;i<len;i++){
		if(s[i]!=s[i-1])
			flag=1;
	}
	if(flag==0){
		PF("1");
		return 0;
	}
	if(len<=3){
		dfs(s);
		int sum=0;
		for(int i=0;i<27;i++)
			if(vis[i]==1)
				sum++;
		PF("%d\n",sum);
		return 0;
	}
	int sum=0;
	for(int i=0;i<len;i++){
		sum+=s[i]-'a';
		sum%=3;
	}
	dp[0][0][0][0]=1;
	for(int i=0;i<len;i++)
		for(int tag=0;tag<2;tag++)
			for(int sum1=0;sum1<3;sum1++)
				for(int las=0;las<3;las++)
					for(int now=0;now<3;now++){
						if(now==las&&i!=0){
							dp[i+1][1][(sum1+now)%3][now]+=dp[i][tag][sum1][las];
							dp[i+1][1][(sum1+now)%3][now]%=MOD;
						}
						else{
							dp[i+1][tag][(sum1+now)%3][now]+=dp[i][tag][sum1][las];
							dp[i+1][tag][(sum1+now)%3][now]%=MOD;
						}
					}
	ll ans=0;
	for(int i=0;i<3;i++)
		ans=(ans+dp[len][1][sum][i])%MOD;
	flag=0;
	for(int i=1;i<len;i++)
		if(s[i]==s[i-1])
			flag=1;
	if(flag==0)
		ans=(ans+1ll)%MOD;
	PF("%lld",ans);
} 
```