#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <string.h>
#include <math.h>
#include <stdio.h>
#include <deque>
#include <bits/stdc++.h>
//#include "testlib.h"
using namespace std;
#define ll long long
#define pii pair<int,int>
#define qi ios::sync_with_stdio(0)

bool debug=true;

/*    *************************************
	  * Written in New Computer           *
	  * The following code belongs to     *
	  * XiaoGeNintendo of HellHoleStudios *
	  *************************************
*/
template<typename T1,typename T2>ostream& operator<<(ostream& os,pair<T1,T2> ptt){
	os<<ptt.first<<","<<ptt.second;
	return os;
}
template<typename T>ostream& operator<<(ostream& os,vector<T> vt){
	os<<"{";
	for(int i=0;i<vt.size();i++){
		os<<vt[i]<<" ";
	}
	os<<"}";
	return os;
}

string s;
int ssum;

const ll mod=998244353;

int dp[200005][4][4][4];

ll dfs(int pos,int par,int last,bool has){
	if(pos==s.size()){
		return has && par==ssum;
	}
	if(dp[pos][par][last][has]!=-1){
		return dp[pos][par][last][has];
	}
	
	ll ans=0;
	ans+=dfs(pos+1,(par+0)%3,0,(last==0)|has);
	ans+=dfs(pos+1,(par+1)%3,1,(last==1)|has);
	ans+=dfs(pos+1,(par+2)%3,2,(last==2)|has);
	ans%=mod;
	return dp[pos][par][last][has]=ans;
}

inline char get(char a,char b){
	if(a>b){
		swap(a,b);
	}
	if(a=='a' && b=='b'){
		return 'c';
	}
	if(a=='a' && b=='c'){
		return 'b';
	}
	if(a=='b' && b=='c'){
		return 'a';
	}
}

set<string> mp;
void force(string s){
	if(mp.count(s)){
		return;
	}
	mp.insert(s);
	
	string ss=s;
	if(s.size()>=2 && s[0]!=s[1]){
		s[0]=s[1]=get(s[0],s[1]);
		force(s);
	}
	if(ss.size()>=3 && ss[1]!=ss[2]){
		ss[1]=ss[2]=get(ss[1],ss[2]);
		force(ss);
	}
}

void brute(){
	force(s);
//	assert(false);
	cout<<mp.size()<<endl;
}
int main(int argc,char* argv[]){
	cin>>s;
	
	if(s.size()<=3){
		brute();
		return 0;
	}
	
	memset(dp,-1,sizeof(dp));
	
	bool allOne=true,allClear=true;
	
	for(int i=0;i<s.size();i++){
		ssum+=s[i]-'a';
		ssum%=3;
		
		if(s[i]!=s[0]){
			allOne=false;
		}
		if(i!=s.size()-1 && s[i]==s[i+1]){
			allClear=false;
		}
	}
	
	if(allOne){
		cout<<1;
		return 0;
	}
	
	int base=dfs(0,0,3,0);
	
	cout<<(base+allClear)%mod<<endl;
	
	return 0;
}


### Prompt

Please provide a CPP coded solution to the problem described below:

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 <algorithm>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <string.h>
#include <math.h>
#include <stdio.h>
#include <deque>
#include <bits/stdc++.h>
//#include "testlib.h"
using namespace std;
#define ll long long
#define pii pair<int,int>
#define qi ios::sync_with_stdio(0)

bool debug=true;

/*    *************************************
	  * Written in New Computer           *
	  * The following code belongs to     *
	  * XiaoGeNintendo of HellHoleStudios *
	  *************************************
*/
template<typename T1,typename T2>ostream& operator<<(ostream& os,pair<T1,T2> ptt){
	os<<ptt.first<<","<<ptt.second;
	return os;
}
template<typename T>ostream& operator<<(ostream& os,vector<T> vt){
	os<<"{";
	for(int i=0;i<vt.size();i++){
		os<<vt[i]<<" ";
	}
	os<<"}";
	return os;
}

string s;
int ssum;

const ll mod=998244353;

int dp[200005][4][4][4];

ll dfs(int pos,int par,int last,bool has){
	if(pos==s.size()){
		return has && par==ssum;
	}
	if(dp[pos][par][last][has]!=-1){
		return dp[pos][par][last][has];
	}
	
	ll ans=0;
	ans+=dfs(pos+1,(par+0)%3,0,(last==0)|has);
	ans+=dfs(pos+1,(par+1)%3,1,(last==1)|has);
	ans+=dfs(pos+1,(par+2)%3,2,(last==2)|has);
	ans%=mod;
	return dp[pos][par][last][has]=ans;
}

inline char get(char a,char b){
	if(a>b){
		swap(a,b);
	}
	if(a=='a' && b=='b'){
		return 'c';
	}
	if(a=='a' && b=='c'){
		return 'b';
	}
	if(a=='b' && b=='c'){
		return 'a';
	}
}

set<string> mp;
void force(string s){
	if(mp.count(s)){
		return;
	}
	mp.insert(s);
	
	string ss=s;
	if(s.size()>=2 && s[0]!=s[1]){
		s[0]=s[1]=get(s[0],s[1]);
		force(s);
	}
	if(ss.size()>=3 && ss[1]!=ss[2]){
		ss[1]=ss[2]=get(ss[1],ss[2]);
		force(ss);
	}
}

void brute(){
	force(s);
//	assert(false);
	cout<<mp.size()<<endl;
}
int main(int argc,char* argv[]){
	cin>>s;
	
	if(s.size()<=3){
		brute();
		return 0;
	}
	
	memset(dp,-1,sizeof(dp));
	
	bool allOne=true,allClear=true;
	
	for(int i=0;i<s.size();i++){
		ssum+=s[i]-'a';
		ssum%=3;
		
		if(s[i]!=s[0]){
			allOne=false;
		}
		if(i!=s.size()-1 && s[i]==s[i+1]){
			allClear=false;
		}
	}
	
	if(allOne){
		cout<<1;
		return 0;
	}
	
	int base=dfs(0,0,3,0);
	
	cout<<(base+allClear)%mod<<endl;
	
	return 0;
}


```