#include<bits/stdc++.h>
using namespace std;
const int mod = 998244353;
bool same(const string& s){
	bool res=true;
	for(int i=1;i<s.size();i++)
		if(s[i]!=s[i-1])
			res=false;
	return res;
}
bool all(const string& s){
	bool res=true;
	for(int i=1;i<s.size();i++)
		if(s[i]==s[i-1])
			res=false;
	return res;
}
long long int dp[200000][3][3][2];
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	string s;
	cin>>s;
	int n=s.size();
	if(same(s))
		cout<<1<<endl;
	else if(n==2)
		cout<<2<<endl;
	else if(n==3){
		if(s[0]!=s[1]&&s[1]!=s[2]&&s[2]!=s[0])
			cout<<3<<endl;
		else if(s[0]==s[2])
			cout<<7<<endl;
		else
			cout<<6<<endl;
	}
	else{
		long long int ans=all(s);
		int sum=0;
		for(int i=0;i<n;i++)
			sum=(sum+s[i]-'a')%3;
		for(int i=0;i<3;i++)
			dp[0][i][i][0]=1;
		for(int i=0;i<n-1;i++)
			for(int j=0;j<3;j++)
				for(int k=0;k<3;k++)
					for(int l=0;l<2;l++)
						for(int m=0;m<3;m++)
							dp[i+1][(j+m)%3][m][l|(m==k)]=(dp[i][j][k][l]+dp[i+1][(j+m)%3][m][l|(m==k)])%mod;
		for(int i=0;i<3;i++)
			ans+=dp[n-1][sum][i][1];
		cout<<ans%mod<<endl;
	}
}

### 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;
const int mod = 998244353;
bool same(const string& s){
	bool res=true;
	for(int i=1;i<s.size();i++)
		if(s[i]!=s[i-1])
			res=false;
	return res;
}
bool all(const string& s){
	bool res=true;
	for(int i=1;i<s.size();i++)
		if(s[i]==s[i-1])
			res=false;
	return res;
}
long long int dp[200000][3][3][2];
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	string s;
	cin>>s;
	int n=s.size();
	if(same(s))
		cout<<1<<endl;
	else if(n==2)
		cout<<2<<endl;
	else if(n==3){
		if(s[0]!=s[1]&&s[1]!=s[2]&&s[2]!=s[0])
			cout<<3<<endl;
		else if(s[0]==s[2])
			cout<<7<<endl;
		else
			cout<<6<<endl;
	}
	else{
		long long int ans=all(s);
		int sum=0;
		for(int i=0;i<n;i++)
			sum=(sum+s[i]-'a')%3;
		for(int i=0;i<3;i++)
			dp[0][i][i][0]=1;
		for(int i=0;i<n-1;i++)
			for(int j=0;j<3;j++)
				for(int k=0;k<3;k++)
					for(int l=0;l<2;l++)
						for(int m=0;m<3;m++)
							dp[i+1][(j+m)%3][m][l|(m==k)]=(dp[i][j][k][l]+dp[i+1][(j+m)%3][m][l|(m==k)])%mod;
		for(int i=0;i<3;i++)
			ans+=dp[n-1][sum][i][1];
		cout<<ans%mod<<endl;
	}
}

```