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

const char P = 'a' ^ 'b' ^ 'c';
const int mod = 998244353;

char s[200010];
queue <string> q;
set <string> all;
int dp[200010][3][3][2];

int main () {
	scanf("%s", s); int n = strlen(s);
	if (n <= 3) {
		q.push(s); all.insert(s);
		while (!q.empty()) {
			string x = q.front(); q.pop();
			for (int i = 0; i < n - 1; i++) {
				if (x[i] != x[i + 1]) {
					string nx = x;
					nx[i] = nx[i + 1] = P ^ nx[i] ^ nx[i + 1];
					if (!all.count(nx)) q.push(nx), all.insert(nx);
				}
			}
		}
		printf("%d\n", all.size());
		return 0;
	}
	int eq = 1;
	for (int i = 0; i < n; i++) {
		eq &= s[i] == s[0];
	}
	if (eq) {
		printf("1\n");
		return 0;
	}
	int sum = 0;
	for (int i = 0; i < n; i++) {
		sum += s[i] - 'a';
	}
	sum %= 3;
	dp[0][0][0][0] = dp[0][1][1][0] = dp[0][2][2][0] = 1;
	for (int i = 0; i < n - 1; i++) {
		for (int j = 0; j < 3; j++) {
			for (int k = 0; k < 3; k++) {
				for (int l = 0; l < 2; l++) {
					for (int x = 0; x < 3; x++) {
						(dp[i + 1][(j + x) % 3][x][l | (x == k)] += dp[i][j][k][l]) %= mod;
					}
				}
			}
		}
	}
	int pd = 1;
	for (int i = 0; i < n - 1; i++) {
		pd &= s[i] != s[i + 1];
	}
	printf("%d\n", ((pd + dp[n - 1][sum][0][1] + dp[n - 1][sum][1][1]) % mod + dp[n - 1][sum][2][1]) % mod);
	return 0;
}

### 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;

const char P = 'a' ^ 'b' ^ 'c';
const int mod = 998244353;

char s[200010];
queue <string> q;
set <string> all;
int dp[200010][3][3][2];

int main () {
	scanf("%s", s); int n = strlen(s);
	if (n <= 3) {
		q.push(s); all.insert(s);
		while (!q.empty()) {
			string x = q.front(); q.pop();
			for (int i = 0; i < n - 1; i++) {
				if (x[i] != x[i + 1]) {
					string nx = x;
					nx[i] = nx[i + 1] = P ^ nx[i] ^ nx[i + 1];
					if (!all.count(nx)) q.push(nx), all.insert(nx);
				}
			}
		}
		printf("%d\n", all.size());
		return 0;
	}
	int eq = 1;
	for (int i = 0; i < n; i++) {
		eq &= s[i] == s[0];
	}
	if (eq) {
		printf("1\n");
		return 0;
	}
	int sum = 0;
	for (int i = 0; i < n; i++) {
		sum += s[i] - 'a';
	}
	sum %= 3;
	dp[0][0][0][0] = dp[0][1][1][0] = dp[0][2][2][0] = 1;
	for (int i = 0; i < n - 1; i++) {
		for (int j = 0; j < 3; j++) {
			for (int k = 0; k < 3; k++) {
				for (int l = 0; l < 2; l++) {
					for (int x = 0; x < 3; x++) {
						(dp[i + 1][(j + x) % 3][x][l | (x == k)] += dp[i][j][k][l]) %= mod;
					}
				}
			}
		}
	}
	int pd = 1;
	for (int i = 0; i < n - 1; i++) {
		pd &= s[i] != s[i + 1];
	}
	printf("%d\n", ((pd + dp[n - 1][sum][0][1] + dp[n - 1][sum][1][1]) % mod + dp[n - 1][sum][2][1]) % mod);
	return 0;
}

```