#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define REP(i,n) for(int i=0;i<(n);i++)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long long ll;

template<class T> inline void read(T &x){
	int f=0;x=0;char ch=getchar();
	for(;!isdigit(ch);ch=getchar())f|=(ch=='-');
	for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';
	if(f)x=-x;
}

const int N=200005,mod=998244353;
int f[N][3][3],n,res;
char s[N];

int chk(){
	rep(i,1,n-1)
		if(s[i]!=s[i+1])return 0;
	return 1;
}

int chk2(){
	rep(i,1,n-1)
		if(s[i]==s[i-1])return 0;
	return 1;
}

int power(int x,int p){
	int res=1;
	for(;p;p>>=1,x=(ll)x*x%mod)
		if(p&1)res=(ll)res*x%mod;
	return res;
}

int main(){
	scanf("%s",s+1);
	n=strlen(s+1);
	if(chk())return puts("1"),0;
	if(n==2)return puts("2"),0;
	if(n==3){
		if(s[1]==s[2]||s[2]==s[3])puts("6");
		else if(s[1]==s[3])puts("7");
		else puts("3");
		return 0;
	}
	int sum=0;
	rep(i,1,n)sum=(sum+s[i]-'a')%3;
	f[1][0][0]=f[1][1][1]=f[1][2][2]=1;
	rep(i,1,n-1)rep(a,0,2)rep(b,0,2)
		rep(c,0,2)if(b!=c)
			f[i+1][(a+c)%3][c]=(f[i+1][(a+c)%3][c]+f[i][a][b])%mod;
	res=(f[n][sum][0]+f[n][sum][1]+1ll*f[n][sum][2])%mod;
	res=(power(3,n-1)+mod-res)%mod;
	if(chk2())res=(res+1)%mod;
	cout<<res<<endl;
	return 0;
}
### 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>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define REP(i,n) for(int i=0;i<(n);i++)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long long ll;

template<class T> inline void read(T &x){
	int f=0;x=0;char ch=getchar();
	for(;!isdigit(ch);ch=getchar())f|=(ch=='-');
	for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';
	if(f)x=-x;
}

const int N=200005,mod=998244353;
int f[N][3][3],n,res;
char s[N];

int chk(){
	rep(i,1,n-1)
		if(s[i]!=s[i+1])return 0;
	return 1;
}

int chk2(){
	rep(i,1,n-1)
		if(s[i]==s[i-1])return 0;
	return 1;
}

int power(int x,int p){
	int res=1;
	for(;p;p>>=1,x=(ll)x*x%mod)
		if(p&1)res=(ll)res*x%mod;
	return res;
}

int main(){
	scanf("%s",s+1);
	n=strlen(s+1);
	if(chk())return puts("1"),0;
	if(n==2)return puts("2"),0;
	if(n==3){
		if(s[1]==s[2]||s[2]==s[3])puts("6");
		else if(s[1]==s[3])puts("7");
		else puts("3");
		return 0;
	}
	int sum=0;
	rep(i,1,n)sum=(sum+s[i]-'a')%3;
	f[1][0][0]=f[1][1][1]=f[1][2][2]=1;
	rep(i,1,n-1)rep(a,0,2)rep(b,0,2)
		rep(c,0,2)if(b!=c)
			f[i+1][(a+c)%3][c]=(f[i+1][(a+c)%3][c]+f[i][a][b])%mod;
	res=(f[n][sum][0]+f[n][sum][1]+1ll*f[n][sum][2])%mod;
	res=(power(3,n-1)+mod-res)%mod;
	if(chk2())res=(res+1)%mod;
	cout<<res<<endl;
	return 0;
}
```