#include <bits/stdc++.h>
using namespace std;
const int MAXN=200200;
const int MOD=998244353;
int N;
int dp[MAXN][3][3][2];
void add(int &x,int y){x+=y;if(x>=MOD)x-=MOD;}
unordered_set<string>vals;
void brute(string S){
	if(vals.count(S))return;
	vals.emplace(S);
	for(int i=0;i+1<N;++i){
		if(S[i]!=S[i+1]){
			char nv='a'+'b'+'c'-S[i]-S[i+1];
			string T=S;
			T[i]=T[i+1]=nv;
			brute(T);
		}
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	string S;
	cin >> S;
	N=S.size();
	if(N <= 3){
		brute(S);
		cout<<int(vals.size())<<"\n";
		return 0;
	}
	for(int i=0;i<3;++i)dp[1][i][i][0]=1;
	for(int i=2;i <= N;++i)
		for(int sum=0;sum<3;++sum)
			for(int last=0;last<3;++last)
				for(int was=0;was<2;++was)
					for(int nxt=0;nxt<3;++nxt)
						add(dp[i][(sum+nxt)%3][nxt][was|(last==nxt)],dp[i-1][sum][last][was]);
	int sum=0;
	bool flagDiff=true,flagSame=true;
	for(int i=0;i<N;++i){
		sum += int(S[i]-'a');
		sum %= 3;
		if(i)flagDiff &=(S[i]!=S[i-1]),flagSame &=(S[i]==S[i-1]);
	}
	int ans=flagDiff;
	for(int i=0;i<3;++i){
		add(ans,dp[N][sum][i][1]);
	}
	if(flagSame)ans=1;
	cout<<ans<<"\n";
	return 0;
}
### Prompt

Please formulate 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 <bits/stdc++.h>
using namespace std;
const int MAXN=200200;
const int MOD=998244353;
int N;
int dp[MAXN][3][3][2];
void add(int &x,int y){x+=y;if(x>=MOD)x-=MOD;}
unordered_set<string>vals;
void brute(string S){
	if(vals.count(S))return;
	vals.emplace(S);
	for(int i=0;i+1<N;++i){
		if(S[i]!=S[i+1]){
			char nv='a'+'b'+'c'-S[i]-S[i+1];
			string T=S;
			T[i]=T[i+1]=nv;
			brute(T);
		}
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	string S;
	cin >> S;
	N=S.size();
	if(N <= 3){
		brute(S);
		cout<<int(vals.size())<<"\n";
		return 0;
	}
	for(int i=0;i<3;++i)dp[1][i][i][0]=1;
	for(int i=2;i <= N;++i)
		for(int sum=0;sum<3;++sum)
			for(int last=0;last<3;++last)
				for(int was=0;was<2;++was)
					for(int nxt=0;nxt<3;++nxt)
						add(dp[i][(sum+nxt)%3][nxt][was|(last==nxt)],dp[i-1][sum][last][was]);
	int sum=0;
	bool flagDiff=true,flagSame=true;
	for(int i=0;i<N;++i){
		sum += int(S[i]-'a');
		sum %= 3;
		if(i)flagDiff &=(S[i]!=S[i-1]),flagSame &=(S[i]==S[i-1]);
	}
	int ans=flagDiff;
	for(int i=0;i<3;++i){
		add(ans,dp[N][sum][i][1]);
	}
	if(flagSame)ans=1;
	cout<<ans<<"\n";
	return 0;
}
```