#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 998244353
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
set<string>S;
string str;
void rec(string s){
	if(S.find(s) != S.end()) return;
	S.insert(s);
	for(int i=1;i<s.size();i++){
		if(s[i-1] != s[i]){
			char ch;
			if(s[i-1] != 'a' && s[i] != 'a') ch = 'a';
			if(s[i-1] != 'b' && s[i] != 'b') ch = 'b';
			if(s[i-1] != 'c' && s[i] != 'c') ch = 'c';
			char p1=s[i-1],p2=s[i];
			s[i-1] = ch;
			s[i] = ch;
			rec(s);
			s[i-1]=p1; s[i]=p2;
		}
	}
}
ll dp[200005][3][3][2];
int main(){
	S.clear();
	cin>>str; int n = str.size();
	if(str.size()<=8){
		rec(str);
		cout << S.size() << endl;
	}
	else{
		int ok = 0;
		int X = 0;
		rep(i,n) X = (X+(str[i]-'a'))%3;
		for(int i=1;i<str.size();i++){
			if(str[i-1] != str[i]) ok += 1;
		}
		if(!ok){
			puts("1"); return 0;
		}
		dp[1][0][0][0] = dp[1][1][1][0] = dp[1][2][2][0] = 1;
		for(int i=1;i<n;i++){
		    for(int j=0;j<3;j++){
		        for(int k=0;k<3;k++){
		            for(int x=0;x<2;x++){
		                for(int nxt=0;nxt<3;nxt++){
		                    dp[i+1][(j+nxt)%3][nxt][(x||(k==nxt))] += dp[i][j][k][x];
		                }
		            }
		        }
		    }
		    rep(j,3) rep(k,3) rep(x,2) dp[i+1][j][k][x]%=mod;
		}
		ll ans = (dp[n][X][0][1]+dp[n][X][1][1]+dp[n][X][2][1])%mod;
		if(ok+1 == n) ans = (ans+1)%mod;
		cout<<ans<<endl;
	}
}
### 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;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 998244353
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
set<string>S;
string str;
void rec(string s){
	if(S.find(s) != S.end()) return;
	S.insert(s);
	for(int i=1;i<s.size();i++){
		if(s[i-1] != s[i]){
			char ch;
			if(s[i-1] != 'a' && s[i] != 'a') ch = 'a';
			if(s[i-1] != 'b' && s[i] != 'b') ch = 'b';
			if(s[i-1] != 'c' && s[i] != 'c') ch = 'c';
			char p1=s[i-1],p2=s[i];
			s[i-1] = ch;
			s[i] = ch;
			rec(s);
			s[i-1]=p1; s[i]=p2;
		}
	}
}
ll dp[200005][3][3][2];
int main(){
	S.clear();
	cin>>str; int n = str.size();
	if(str.size()<=8){
		rec(str);
		cout << S.size() << endl;
	}
	else{
		int ok = 0;
		int X = 0;
		rep(i,n) X = (X+(str[i]-'a'))%3;
		for(int i=1;i<str.size();i++){
			if(str[i-1] != str[i]) ok += 1;
		}
		if(!ok){
			puts("1"); return 0;
		}
		dp[1][0][0][0] = dp[1][1][1][0] = dp[1][2][2][0] = 1;
		for(int i=1;i<n;i++){
		    for(int j=0;j<3;j++){
		        for(int k=0;k<3;k++){
		            for(int x=0;x<2;x++){
		                for(int nxt=0;nxt<3;nxt++){
		                    dp[i+1][(j+nxt)%3][nxt][(x||(k==nxt))] += dp[i][j][k][x];
		                }
		            }
		        }
		    }
		    rep(j,3) rep(k,3) rep(x,2) dp[i+1][j][k][x]%=mod;
		}
		ll ans = (dp[n][X][0][1]+dp[n][X][1][1]+dp[n][X][2][1])%mod;
		if(ok+1 == n) ans = (ans+1)%mod;
		cout<<ans<<endl;
	}
}
```