#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 200005, mod = 998244353;

ll n, s, dt[N][2][3][3];
char a[N];

int main()
{
	scanf("%s",a+1);
	n = strlen(a+1);
	if(n == 2) {
		if(a[1] == a[2]) puts("1");
		else puts("2");
		return 0;
	}
	if(n == 3) {
		bool A = (a[1] != a[2]), B = (a[2] != a[3]), C = (a[3] != a[1]);
		if(A && B && C) puts("3");
		else if(!A && !B && !C) puts("1");
		else if(C) puts("6");
		else puts("7");
		return 0;
	}
	ll F = 1, G = 1;
	for(int i=2;i<=n;i++) {
		if(a[i] == a[i-1]) F = 0;
		if(a[i] != a[i-1]) G = 0;
	}
	if(G) {puts("1"); return 0;}
	for(int i=1;i<=n;i++) {
		a[i] -= 'a';
		s += a[i];
	}
	s %= 3;
	dt[1][0][0][0] = 1;
	dt[1][0][1][1] = 1;
	dt[1][0][2][2] = 1;
	for(int i=2;i<=n;i++) {
		for(int x=0;x<2;x++) for(int j=0;j<3;j++) for(int k=0;k<3;k++) for(int l=0;l<3;l++) {
			dt[i][x|(k==l)][(j+l)%3][l] += dt[i-1][x][j][k];
			dt[i][x|(k==l)][(j+l)%3][l] %= mod;
		}
	}
	printf("%lld",(dt[n][1][s][0]+dt[n][1][s][1]+dt[n][1][s][2]+F)%mod);
}

### 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<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 200005, mod = 998244353;

ll n, s, dt[N][2][3][3];
char a[N];

int main()
{
	scanf("%s",a+1);
	n = strlen(a+1);
	if(n == 2) {
		if(a[1] == a[2]) puts("1");
		else puts("2");
		return 0;
	}
	if(n == 3) {
		bool A = (a[1] != a[2]), B = (a[2] != a[3]), C = (a[3] != a[1]);
		if(A && B && C) puts("3");
		else if(!A && !B && !C) puts("1");
		else if(C) puts("6");
		else puts("7");
		return 0;
	}
	ll F = 1, G = 1;
	for(int i=2;i<=n;i++) {
		if(a[i] == a[i-1]) F = 0;
		if(a[i] != a[i-1]) G = 0;
	}
	if(G) {puts("1"); return 0;}
	for(int i=1;i<=n;i++) {
		a[i] -= 'a';
		s += a[i];
	}
	s %= 3;
	dt[1][0][0][0] = 1;
	dt[1][0][1][1] = 1;
	dt[1][0][2][2] = 1;
	for(int i=2;i<=n;i++) {
		for(int x=0;x<2;x++) for(int j=0;j<3;j++) for(int k=0;k<3;k++) for(int l=0;l<3;l++) {
			dt[i][x|(k==l)][(j+l)%3][l] += dt[i-1][x][j][k];
			dt[i][x|(k==l)][(j+l)%3][l] %= mod;
		}
	}
	printf("%lld",(dt[n][1][s][0]+dt[n][1][s][1]+dt[n][1][s][2]+F)%mod);
}

```