#include <bits/stdc++.h>
using namespace std;
typedef signed long long ll;

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------


string S;
int N;
ll mo=998244353;
ll dp[202020][2][3][3];

void solve() {
	int i,j,k,l,r,x,y,z; string s;
	
	cin>>S;
	N=S.size();
	
	if(N<=7) {
		set<string> T,R;
		T.insert(S);
		while(T.size()) {
			set<string> U;
			FORR(t,T) {
				R.insert(t);
				FOR(i,N-1) {
					if(t[i]!=t[i+1]) {
						string a=t;
						a[i]=a[i+1]='a'+'b'+'c'-a[i]-a[i+1];
						if(R.count(a)==0) {
							U.insert(a);
							R.insert(a);
						}
					}
				}
				
			}
			T=U;
		}
		cout<<R.size()<<endl;
		return;
	}
	
	int cnt[3]={};
	int tot=0;
	FORR(c,S) {
		c-='a';
		cnt[c]++;
		tot+=c;
	}
	
	if(cnt[0]==N || cnt[1]==N || cnt[2]==N) return _P("1\n");
	
	dp[1][0][0][0]=1;
	dp[1][0][1][1]=1;
	dp[1][0][2][2]=1;
	for(i=1;i<N;i++) {
		
		FOR(j,2) FOR(x,3) FOR(y,3) FOR(z,3) {
			(dp[i+1][j|(x==z)][z][(y+z)%3]+=dp[i][j][x][y])%=mo;
		}
	}
	
	ll ret=1;
	FOR(i,3) ret+=dp[N][1][i][tot%3];
	FOR(i,N-1) if(S[i]==S[i+1]) {
		ret--;
		break;
	}
	cout<<ret%mo<<endl;
	
	
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); 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 signed long long ll;

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------


string S;
int N;
ll mo=998244353;
ll dp[202020][2][3][3];

void solve() {
	int i,j,k,l,r,x,y,z; string s;
	
	cin>>S;
	N=S.size();
	
	if(N<=7) {
		set<string> T,R;
		T.insert(S);
		while(T.size()) {
			set<string> U;
			FORR(t,T) {
				R.insert(t);
				FOR(i,N-1) {
					if(t[i]!=t[i+1]) {
						string a=t;
						a[i]=a[i+1]='a'+'b'+'c'-a[i]-a[i+1];
						if(R.count(a)==0) {
							U.insert(a);
							R.insert(a);
						}
					}
				}
				
			}
			T=U;
		}
		cout<<R.size()<<endl;
		return;
	}
	
	int cnt[3]={};
	int tot=0;
	FORR(c,S) {
		c-='a';
		cnt[c]++;
		tot+=c;
	}
	
	if(cnt[0]==N || cnt[1]==N || cnt[2]==N) return _P("1\n");
	
	dp[1][0][0][0]=1;
	dp[1][0][1][1]=1;
	dp[1][0][2][2]=1;
	for(i=1;i<N;i++) {
		
		FOR(j,2) FOR(x,3) FOR(y,3) FOR(z,3) {
			(dp[i+1][j|(x==z)][z][(y+z)%3]+=dp[i][j][x][y])%=mo;
		}
	}
	
	ll ret=1;
	FOR(i,3) ret+=dp[N][1][i][tot%3];
	FOR(i,N-1) if(S[i]==S[i+1]) {
		ret--;
		break;
	}
	cout<<ret%mo<<endl;
	
	
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}

```