#include <iostream>
#include <algorithm>
#include <cmath>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <string.h>
#include <stack>
#include <assert.h>
#include <bitset>
#define Endl endl
#define mp make_pair
#define ll long long 
#define pii pair<int,int>
#define pll pair<ll,ll>
#define over(A) {cout<<A<<endl;exit(0);}
#define all(A) A.begin(),A.end()
#define ceil(a,b) ((a-1)/b+1)
#define srand() mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rand(l,r) uniform_int_distribution<int>(l,r)(rng)
typedef unsigned long long ull;
const int inf=1039074182;
using namespace std;
char c[200005];
int n;
map <string,bool> m;
char ch[256];
int dp[200005][3][3];
int f[200005][3];
const int mod=998244353;

void dfs(string s)
{
	if(m[s]) return;
	string t=s;
	m[s]=true;
	for(int i=0;i<(int)s.size()-1;i++)
	{
		if(s[i]!=s[i+1])
		{
			ch['a']=ch['b']=ch['c']=false;
			ch[s[i]]=true;
			ch[s[i+1]]=true;
			for(char cc='a';cc<='c';cc++)
			{
				if(ch[cc]) continue;
				s[i]=s[i+1]=cc;
				dfs(s);
				s=t;
				break;
			}
		}
	}
}

int main() 
{
//	freopen("input.txt","r",stdin);
	scanf("%s",c);
	n=strlen(c);
	if(n<=5)
	{
		string s=c;
		dfs(s);
		cout<<m.size()<<endl;
		return 0;
	}
//	for(auto x:m)
//	{
//		cout<<x.first<<endl;
//	}
//	cout<<m.size()<<endl;
	dp[1][0][0]=dp[1][1][1]=dp[1][2][2]=1;
	for(int i=1;i<n;i++)
	{
		for(int s=0;s<3;s++)
		{
			for(int last=0;last<3;last++)
			{
				for(int newadd=0;newadd<3;newadd++)
				{
					if(last==newadd) continue;
					int& tr=dp[i+1][(s+newadd)%3][newadd];
					tr+=dp[i][s][last];
					if(tr>=mod) tr-=mod;
				}
			}
		}
	}
	f[0][0]=1;
	for(int i=0;i<n;i++)
	{
		for(int s=0;s<3;s++)
		{
			for(int newadd=0;newadd<3;newadd++)
			{
				int& tr=f[i+1][(s+newadd)%3];
				tr+=f[i][s];
				if(tr>=mod) tr-=mod;
			}
		}
	}
	
	bool flag=true;
	for(int i=0;i<n;i++)
	{
		if(c[i]!=c[0]) flag=false;
	}
	if(flag) over(1);
	
	bool diffall=true;
	for(int i=0;i<n-1;i++)
	{
		if(c[i]==c[i+1]) diffall=false;
	}
	
	int s=0;
	for(int i=0;i<n;i++)
	{
		s+=c[i]-'a';
	}
	s%=3;
	
	cout<<((ll)f[n][s]-dp[n][s][0]-dp[n][s][1]-dp[n][s][2]+1LL*mod*5+diffall)%mod<<endl;
	return 0;
}
### Prompt

Develop a solution in cpp 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 <cmath>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <string.h>
#include <stack>
#include <assert.h>
#include <bitset>
#define Endl endl
#define mp make_pair
#define ll long long 
#define pii pair<int,int>
#define pll pair<ll,ll>
#define over(A) {cout<<A<<endl;exit(0);}
#define all(A) A.begin(),A.end()
#define ceil(a,b) ((a-1)/b+1)
#define srand() mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rand(l,r) uniform_int_distribution<int>(l,r)(rng)
typedef unsigned long long ull;
const int inf=1039074182;
using namespace std;
char c[200005];
int n;
map <string,bool> m;
char ch[256];
int dp[200005][3][3];
int f[200005][3];
const int mod=998244353;

void dfs(string s)
{
	if(m[s]) return;
	string t=s;
	m[s]=true;
	for(int i=0;i<(int)s.size()-1;i++)
	{
		if(s[i]!=s[i+1])
		{
			ch['a']=ch['b']=ch['c']=false;
			ch[s[i]]=true;
			ch[s[i+1]]=true;
			for(char cc='a';cc<='c';cc++)
			{
				if(ch[cc]) continue;
				s[i]=s[i+1]=cc;
				dfs(s);
				s=t;
				break;
			}
		}
	}
}

int main() 
{
//	freopen("input.txt","r",stdin);
	scanf("%s",c);
	n=strlen(c);
	if(n<=5)
	{
		string s=c;
		dfs(s);
		cout<<m.size()<<endl;
		return 0;
	}
//	for(auto x:m)
//	{
//		cout<<x.first<<endl;
//	}
//	cout<<m.size()<<endl;
	dp[1][0][0]=dp[1][1][1]=dp[1][2][2]=1;
	for(int i=1;i<n;i++)
	{
		for(int s=0;s<3;s++)
		{
			for(int last=0;last<3;last++)
			{
				for(int newadd=0;newadd<3;newadd++)
				{
					if(last==newadd) continue;
					int& tr=dp[i+1][(s+newadd)%3][newadd];
					tr+=dp[i][s][last];
					if(tr>=mod) tr-=mod;
				}
			}
		}
	}
	f[0][0]=1;
	for(int i=0;i<n;i++)
	{
		for(int s=0;s<3;s++)
		{
			for(int newadd=0;newadd<3;newadd++)
			{
				int& tr=f[i+1][(s+newadd)%3];
				tr+=f[i][s];
				if(tr>=mod) tr-=mod;
			}
		}
	}
	
	bool flag=true;
	for(int i=0;i<n;i++)
	{
		if(c[i]!=c[0]) flag=false;
	}
	if(flag) over(1);
	
	bool diffall=true;
	for(int i=0;i<n-1;i++)
	{
		if(c[i]==c[i+1]) diffall=false;
	}
	
	int s=0;
	for(int i=0;i<n;i++)
	{
		s+=c[i]-'a';
	}
	s%=3;
	
	cout<<((ll)f[n][s]-dp[n][s][0]-dp[n][s][1]-dp[n][s][2]+1LL*mod*5+diffall)%mod<<endl;
	return 0;
}
```