#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int maxn=200003;
const int mo=998244353;

int f[maxn][3][3][2],n;
char s[maxn];

void add(int &x,int y){
	x+=y;
	if(x>=mo)x-=mo;
}

void solve(){
	scanf("%s",s+1);
	n=strlen(s+1);
	int want=s[1]-'a',ret=1;
	bool flag=true;
	for(int i=2;i<=n;++i){
		if(s[i]!=s[1])flag=false;
		want+=s[i]-'a';
		ret&=(s[i]!=s[i-1]);
	}
	if(flag){
		puts("1");
		return ;
	}
	if(n==2){
		puts("2");
		return ;
	}
	if(n==3&&s[1]!=s[2]&&s[3]!=s[2]&&s[1]!=s[3]){
		puts("3");
		return ;
	}
	want%=3;
	for(int i=0;i<3;++i)f[1][i][i][0]=1;
	for(int i=1;i<n;++i)
		for(int last=0;last<3;++last)
			for(int sum=0;sum<3;++sum)
				for(int adj=0;adj<2;++adj){
					for(int c=0;c<3;++c){
						int nsum=(sum+c)%3,nadj=adj|(last==c);
						add(f[i+1][c][nsum][nadj],f[i][last][sum][adj]);
					}
				}
	for(int i=0;i<3;++i)
		add(ret,f[n][i][want][1]);
	printf("%d\n",ret);
}


int main(){
	solve();
	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<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int maxn=200003;
const int mo=998244353;

int f[maxn][3][3][2],n;
char s[maxn];

void add(int &x,int y){
	x+=y;
	if(x>=mo)x-=mo;
}

void solve(){
	scanf("%s",s+1);
	n=strlen(s+1);
	int want=s[1]-'a',ret=1;
	bool flag=true;
	for(int i=2;i<=n;++i){
		if(s[i]!=s[1])flag=false;
		want+=s[i]-'a';
		ret&=(s[i]!=s[i-1]);
	}
	if(flag){
		puts("1");
		return ;
	}
	if(n==2){
		puts("2");
		return ;
	}
	if(n==3&&s[1]!=s[2]&&s[3]!=s[2]&&s[1]!=s[3]){
		puts("3");
		return ;
	}
	want%=3;
	for(int i=0;i<3;++i)f[1][i][i][0]=1;
	for(int i=1;i<n;++i)
		for(int last=0;last<3;++last)
			for(int sum=0;sum<3;++sum)
				for(int adj=0;adj<2;++adj){
					for(int c=0;c<3;++c){
						int nsum=(sum+c)%3,nadj=adj|(last==c);
						add(f[i+1][c][nsum][nadj],f[i][last][sum][adj]);
					}
				}
	for(int i=0;i<3;++i)
		add(ret,f[n][i][want][1]);
	printf("%d\n",ret);
}


int main(){
	solve();
	return 0;
}


```