#include<stdio.h>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#define re register 
using namespace std;
const int mod = 998244353;
int ad(int x,int y) { x+=y; return x>=mod?x-mod:x; }
int sb(int x,int y) { x-=y; return x<0?x+mod:x; }
int mu(int x,int y) { return 1ll*x*y%mod; }
void up(int &x,int y) { x+=y; x%=mod; }
int f[200005][3][3][2];//mod lst 0/1
char ss[200005];
int n,SM;

void tp() {
	if(ss[1]!=ss[2]&&ss[2]!=ss[3]&&ss[1]!=ss[3]) puts("3");
	else if(ss[1]==ss[2]&&ss[2]==ss[3]) puts("1"); 
	else if(ss[1]==ss[3]) puts("7");
	else puts("6");//ss1==ss2||ss2==ss3
} 

int main() {
	scanf("%s",&ss[1]);
	n = strlen(ss+1);
	
	if(n==3) {
		tp(); return 0;
	}
	
	for(int i=0;i<=2;i++) f[1][i][i][0] = 1;
	bool mk = 0;
	bool mm = 0;
	ss[0] = 233;
	for(int i=1;i<=n;i++) {
		ss[i]-='a'; SM+=ss[i]; SM%=3;
		if(ss[i]==ss[i-1]) mk = 1;
		if(i!=1&&ss[i]!=ss[i-1]) mm = 1;
	}
	if(!mm) {
		puts("1"); return 0;
	}
	int ans = 0;
	if(!mk) ans = 1;
	for(re int i=1;i<=n-1;i++) {
		for(re int j=0;j<=2;j++) {
			for(re int k=0;k<=2;k++) {
				for(re int o=0;o<=1;o++) {
					if(!f[i][j][k][o]) continue;
					for(re int d=0;d<=2;d++) {
						up(f[i+1][(j+d)%3][d][o|(d==k?1:0)],f[i][j][k][o]);
					}
				}
			}
		}
	}
	//100000 * (3^3) * 2 == 5400000
	for(int i=0;i<=2;i++) {
		up(ans,f[n][SM][i][1]);
	}
	printf("%d",ans);
}
### Prompt

Your task is to create 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<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#define re register 
using namespace std;
const int mod = 998244353;
int ad(int x,int y) { x+=y; return x>=mod?x-mod:x; }
int sb(int x,int y) { x-=y; return x<0?x+mod:x; }
int mu(int x,int y) { return 1ll*x*y%mod; }
void up(int &x,int y) { x+=y; x%=mod; }
int f[200005][3][3][2];//mod lst 0/1
char ss[200005];
int n,SM;

void tp() {
	if(ss[1]!=ss[2]&&ss[2]!=ss[3]&&ss[1]!=ss[3]) puts("3");
	else if(ss[1]==ss[2]&&ss[2]==ss[3]) puts("1"); 
	else if(ss[1]==ss[3]) puts("7");
	else puts("6");//ss1==ss2||ss2==ss3
} 

int main() {
	scanf("%s",&ss[1]);
	n = strlen(ss+1);
	
	if(n==3) {
		tp(); return 0;
	}
	
	for(int i=0;i<=2;i++) f[1][i][i][0] = 1;
	bool mk = 0;
	bool mm = 0;
	ss[0] = 233;
	for(int i=1;i<=n;i++) {
		ss[i]-='a'; SM+=ss[i]; SM%=3;
		if(ss[i]==ss[i-1]) mk = 1;
		if(i!=1&&ss[i]!=ss[i-1]) mm = 1;
	}
	if(!mm) {
		puts("1"); return 0;
	}
	int ans = 0;
	if(!mk) ans = 1;
	for(re int i=1;i<=n-1;i++) {
		for(re int j=0;j<=2;j++) {
			for(re int k=0;k<=2;k++) {
				for(re int o=0;o<=1;o++) {
					if(!f[i][j][k][o]) continue;
					for(re int d=0;d<=2;d++) {
						up(f[i+1][(j+d)%3][d][o|(d==k?1:0)],f[i][j][k][o]);
					}
				}
			}
		}
	}
	//100000 * (3^3) * 2 == 5400000
	for(int i=0;i<=2;i++) {
		up(ans,f[n][SM][i][1]);
	}
	printf("%d",ans);
}
```