#include <iostream>
#include<bits/stdc++.h>
#include<string>
#include<vector>
using namespace std;
typedef long long ll;
vector<vector<vector<vector<ll>>>> dp;
ll def;
ll solve(int n,int mod,int ch,int same){
	if(n==1){
		if(same==1){
			return 0;
		}
		if(mod==ch){
			return 1;
		}
		return 0;
	}
	ll &ans=dp[n][mod][ch][same];
	if(~ans)return ans;
	ans=0;
	mod+=3-ch;
	mod%=3;
	if(same){
		for(int i=0;i<3;i++){
			ans+=solve(n-1,mod,i,1);
		}
		ans+=solve(n-1,mod,ch,0);
	}else{
		for(int i=0;i<3;i++){
			if(i!=ch){
			ans+=solve(n-1,mod,i,0);
			}
		}
	}
	ans%=def;
	return ans;
}

int main() {
	 def=998244353;
	string s;cin>>s;
	for(int i=1;i<s.size();i++){
		if(s[i]!=s[i-1])break;
		if(i==s.size()-1){
			cout<<1<<endl;
			return 0;
		}
	}
	if(s.size()==2){
		if(s[0]==s[1]){
			cout<<1<<endl;
			return 0;
		}else{
			cout<<2<<endl;
			return 0;
		}
	}else if(s.size()==3){
		int ans;
		if(s[0]==s[1]){
			if(s[1]==s[2]){
				ans=1;
			}else{
				ans=6;
			}
		}else{
			if(s[1]==s[2]){
				ans=6;
			}else{
				if(s[0]==s[2]){
					ans=7;
				}else{
					ans=3;
				}
			}
		}

		cout<<ans<<endl;
		return 0;

	}
//	memset(dp,-1,sizeof(dp));
	dp=vector<vector<vector<vector<ll>>>>(200001,vector<vector<vector<ll>>>(3,vector<vector<ll>>(3,vector<ll>(2,-1))));
	ll ans=0;
	ll rem=0;
	ll flag=1;
	for(int i=0;i<s.size();i++){
		rem+=int(s[i]-'a');
	}
	rem%=3;
	for(int i=1;i<s.size();i++){
		if(s[i]==s[i-1])flag=0;
	}

		ans+=solve(s.size(),rem,0,1);
		ans+=solve(s.size(),rem,1,1);
		ans+=solve(s.size(),rem,2,1);
		ans+=flag;

	cout<<ans%def<<endl;
	return 0;
}
### Prompt

Construct a Cpp code solution to the problem outlined:

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 <iostream>
#include<bits/stdc++.h>
#include<string>
#include<vector>
using namespace std;
typedef long long ll;
vector<vector<vector<vector<ll>>>> dp;
ll def;
ll solve(int n,int mod,int ch,int same){
	if(n==1){
		if(same==1){
			return 0;
		}
		if(mod==ch){
			return 1;
		}
		return 0;
	}
	ll &ans=dp[n][mod][ch][same];
	if(~ans)return ans;
	ans=0;
	mod+=3-ch;
	mod%=3;
	if(same){
		for(int i=0;i<3;i++){
			ans+=solve(n-1,mod,i,1);
		}
		ans+=solve(n-1,mod,ch,0);
	}else{
		for(int i=0;i<3;i++){
			if(i!=ch){
			ans+=solve(n-1,mod,i,0);
			}
		}
	}
	ans%=def;
	return ans;
}

int main() {
	 def=998244353;
	string s;cin>>s;
	for(int i=1;i<s.size();i++){
		if(s[i]!=s[i-1])break;
		if(i==s.size()-1){
			cout<<1<<endl;
			return 0;
		}
	}
	if(s.size()==2){
		if(s[0]==s[1]){
			cout<<1<<endl;
			return 0;
		}else{
			cout<<2<<endl;
			return 0;
		}
	}else if(s.size()==3){
		int ans;
		if(s[0]==s[1]){
			if(s[1]==s[2]){
				ans=1;
			}else{
				ans=6;
			}
		}else{
			if(s[1]==s[2]){
				ans=6;
			}else{
				if(s[0]==s[2]){
					ans=7;
				}else{
					ans=3;
				}
			}
		}

		cout<<ans<<endl;
		return 0;

	}
//	memset(dp,-1,sizeof(dp));
	dp=vector<vector<vector<vector<ll>>>>(200001,vector<vector<vector<ll>>>(3,vector<vector<ll>>(3,vector<ll>(2,-1))));
	ll ans=0;
	ll rem=0;
	ll flag=1;
	for(int i=0;i<s.size();i++){
		rem+=int(s[i]-'a');
	}
	rem%=3;
	for(int i=1;i<s.size();i++){
		if(s[i]==s[i-1])flag=0;
	}

		ans+=solve(s.size(),rem,0,1);
		ans+=solve(s.size(),rem,1,1);
		ans+=solve(s.size(),rem,2,1);
		ans+=flag;

	cout<<ans%def<<endl;
	return 0;
}
```