#include <stdio.h>
#include <string>
#include <queue>
#include <set>
using namespace std;

const int mod = 998244353;
int prv[3][3][2], nxt[3][3][2];
char S[200200];

int main()
{
	scanf ("%s",S);

	int l = 0;
	while (S[l]) l++;

	if (l <= 10){
		set<string> chk;
		queue<string> Q;
		Q.push(S); chk.insert(S);
		while (!Q.empty()){
			string s = Q.front(); Q.pop();
			for (int i=1;i<s.length();i++) if (s[i-1] != s[i]){
				string t = s;
				int c = 3 - (s[i-1] - 'a') - (s[i] - 'a') + 'a';
				t[i-1] = t[i] = c;
				if (!chk.count(t)){
					Q.push(t); chk.insert(t);
				}
			}
		}
		printf ("%d\n",chk.size());
		return 0;
	}

	int c = 0;
	for (int i=0;i<l;i++) c += S[i] - 'a';

	bool p = false, q = false;
	for (int i=1;i<l;i++){
		if (S[i-1] == S[i]) p = true;
		if (S[i-1] != S[i]) q = true;
	}

	prv[0][0][0] = prv[0][1][0] = prv[0][2][0] = 1;
	for (int i=1;i<l;i++){
		for (int x=0;x<3;x++) for (int y=0;y<3;y++) for (int k=0;k<2;k++) nxt[x][y][k] = 0;
		for (int x=0;x<3;x++) for (int y=0;y<3;y++) for (int k=0;k<2;k++){
			for (int z=0;z<3;z++){
				int nk = k || ((x + y + z) % 3 == 0);
				nxt[y][z][nk] = (nxt[y][z][nk] + prv[x][y][k]) % mod;
			}
		}
		for (int x=0;x<3;x++) for (int y=0;y<3;y++) for (int k=0;k<2;k++) prv[x][y][k] = nxt[x][y][k];
	}

	if (!q) puts("1");
	else{
		int ans = !p;
		for (int x=0;x<3;x++) ans = (ans + prv[x][c%3][1]) % mod;
		printf ("%d\n",ans);
	}

	return 0;
}
### Prompt

Your challenge is to write 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 <string>
#include <queue>
#include <set>
using namespace std;

const int mod = 998244353;
int prv[3][3][2], nxt[3][3][2];
char S[200200];

int main()
{
	scanf ("%s",S);

	int l = 0;
	while (S[l]) l++;

	if (l <= 10){
		set<string> chk;
		queue<string> Q;
		Q.push(S); chk.insert(S);
		while (!Q.empty()){
			string s = Q.front(); Q.pop();
			for (int i=1;i<s.length();i++) if (s[i-1] != s[i]){
				string t = s;
				int c = 3 - (s[i-1] - 'a') - (s[i] - 'a') + 'a';
				t[i-1] = t[i] = c;
				if (!chk.count(t)){
					Q.push(t); chk.insert(t);
				}
			}
		}
		printf ("%d\n",chk.size());
		return 0;
	}

	int c = 0;
	for (int i=0;i<l;i++) c += S[i] - 'a';

	bool p = false, q = false;
	for (int i=1;i<l;i++){
		if (S[i-1] == S[i]) p = true;
		if (S[i-1] != S[i]) q = true;
	}

	prv[0][0][0] = prv[0][1][0] = prv[0][2][0] = 1;
	for (int i=1;i<l;i++){
		for (int x=0;x<3;x++) for (int y=0;y<3;y++) for (int k=0;k<2;k++) nxt[x][y][k] = 0;
		for (int x=0;x<3;x++) for (int y=0;y<3;y++) for (int k=0;k<2;k++){
			for (int z=0;z<3;z++){
				int nk = k || ((x + y + z) % 3 == 0);
				nxt[y][z][nk] = (nxt[y][z][nk] + prv[x][y][k]) % mod;
			}
		}
		for (int x=0;x<3;x++) for (int y=0;y<3;y++) for (int k=0;k<2;k++) prv[x][y][k] = nxt[x][y][k];
	}

	if (!q) puts("1");
	else{
		int ans = !p;
		for (int x=0;x<3;x++) ans = (ans + prv[x][c%3][1]) % mod;
		printf ("%d\n",ans);
	}

	return 0;
}
```