#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
using namespace std;
const long long mod=998244353;
const long long inf=mod*mod;
const long long d2=(mod+1)/2;
const double EPS=1e-10;
const double INF=1e+10;
const double PI=acos(-1.0);
const int C_SIZE = 3121000;
long long fact[C_SIZE];
long long finv[C_SIZE];
long long inv[C_SIZE];
long long Comb(int a,int b){
 	if(a<b||b<0)return 0;
 	return fact[a]*finv[b]%mod*finv[a-b]%mod;
}
void init_C(int n){
	fact[0]=finv[0]=inv[1]=1;
	for(int i=2;i<n;i++){
		inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
	}
	for(int i=1;i<n;i++){
		fact[i]=fact[i-1]*i%mod;
		finv[i]=finv[i-1]*inv[i]%mod;
	}
}
long long pw(long long a,long long b){
	if(a<0LL)return 0;
	long long ret=1;
	while(b){
		if(b%2)ret=ret*a%mod;
		a=a*a%mod;
		b/=2;
	}
	return ret;
}
int ABS(int a){return max(a,-a);}
long long ABS(long long a){return max(a,-a);}
double ABS(double a){return max(a,-a);}
// ここから編集しろ
char in[210000];
long long dp[210000][3][3];
int main(){
	scanf("%s",in);
	int n=strlen(in);
	if(n==2){
		if(in[0]==in[1])printf("1\n");
		else printf("2\n");return 0;
	}
	int f=0;
	for(int i=0;i<n;i++)f+=in[i]-'a';
	f%=3;

	int t=1;
	int u=1;
	for(int i=0;i<n-1;i++){if(in[i]==in[i+1])t=0;else u=0;}
	if(u){
		printf("1\n");return 0;
	}
	if(n==3&&f==0){
		int ret=1;
		if(t)ret+=2;
		printf("%d\n",ret);return 0;
	}
	long long ret=pw(3,n-1);
	dp[1][0][0]=dp[1][1][1]=dp[1][2][2]=1;
	for(int i=1;i<n;i++){
		for(int j=0;j<3;j++)for(int k=0;k<3;k++){
			if(dp[i][j][k]==0)continue;
			for(int l=0;l<3;l++){
				if(k==l)continue;
				dp[i+1][(j+l)%3][l]=(dp[i+1][(j+l)%3][l]+dp[i][j][k])%mod;
			}
		}
	}
	ret=(ret+mod-dp[n][f][0])%mod;
	ret=(ret+mod-dp[n][f][1])%mod;
	ret=(ret+mod-dp[n][f][2])%mod;
	
	ret=(ret+t)%mod;

	printf("%lld\n",ret);
}

### Prompt

Please formulate a cpp solution to 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<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
using namespace std;
const long long mod=998244353;
const long long inf=mod*mod;
const long long d2=(mod+1)/2;
const double EPS=1e-10;
const double INF=1e+10;
const double PI=acos(-1.0);
const int C_SIZE = 3121000;
long long fact[C_SIZE];
long long finv[C_SIZE];
long long inv[C_SIZE];
long long Comb(int a,int b){
 	if(a<b||b<0)return 0;
 	return fact[a]*finv[b]%mod*finv[a-b]%mod;
}
void init_C(int n){
	fact[0]=finv[0]=inv[1]=1;
	for(int i=2;i<n;i++){
		inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
	}
	for(int i=1;i<n;i++){
		fact[i]=fact[i-1]*i%mod;
		finv[i]=finv[i-1]*inv[i]%mod;
	}
}
long long pw(long long a,long long b){
	if(a<0LL)return 0;
	long long ret=1;
	while(b){
		if(b%2)ret=ret*a%mod;
		a=a*a%mod;
		b/=2;
	}
	return ret;
}
int ABS(int a){return max(a,-a);}
long long ABS(long long a){return max(a,-a);}
double ABS(double a){return max(a,-a);}
// ここから編集しろ
char in[210000];
long long dp[210000][3][3];
int main(){
	scanf("%s",in);
	int n=strlen(in);
	if(n==2){
		if(in[0]==in[1])printf("1\n");
		else printf("2\n");return 0;
	}
	int f=0;
	for(int i=0;i<n;i++)f+=in[i]-'a';
	f%=3;

	int t=1;
	int u=1;
	for(int i=0;i<n-1;i++){if(in[i]==in[i+1])t=0;else u=0;}
	if(u){
		printf("1\n");return 0;
	}
	if(n==3&&f==0){
		int ret=1;
		if(t)ret+=2;
		printf("%d\n",ret);return 0;
	}
	long long ret=pw(3,n-1);
	dp[1][0][0]=dp[1][1][1]=dp[1][2][2]=1;
	for(int i=1;i<n;i++){
		for(int j=0;j<3;j++)for(int k=0;k<3;k++){
			if(dp[i][j][k]==0)continue;
			for(int l=0;l<3;l++){
				if(k==l)continue;
				dp[i+1][(j+l)%3][l]=(dp[i+1][(j+l)%3][l]+dp[i][j][k])%mod;
			}
		}
	}
	ret=(ret+mod-dp[n][f][0])%mod;
	ret=(ret+mod-dp[n][f][1])%mod;
	ret=(ret+mod-dp[n][f][2])%mod;
	
	ret=(ret+t)%mod;

	printf("%lld\n",ret);
}

```