#include <bits/stdc++.h>

using namespace std;

#define SZ(x) ((int)x.size())

const int N = (int)2e5+5;
const int mod = 998244353;
int n, m, dp[N][3], dp2[N][3][3];
string s;

char change(char x, char y) {
	if ((x == 'a' && y == 'b') || (x == 'b' && y == 'a')) return 'c';
	if ((x == 'c' && y == 'b') || (x == 'b' && y == 'c')) return 'a';
	return 'b';
}

void gen_all() {
	map<string, bool> vis;
	queue<string> q;
	q.push(s);
	vis[s] = true;
	while (SZ(q)) {
		string u = q.front(); q.pop();
		for (int i = 0; i < n - 1; ++i) {
			if (u[i] == u[i + 1]) continue;
			string v = "";
			v.assign(u);
			char now = change(v[i], v[i + 1]);
			v[i] = now, v[i + 1] = now;
			if (vis[v]) continue;
			vis[v] = true;
			q.push(v);
		}
	}
	cout << SZ(vis) << "\n";
}

int main() {
	cin >> s;
	n = SZ(s);
	int add = 1;
	bool all_same = true;
	for (int i = 0; i < n; ++i) {
		m = (m + s[i] - 'a') % 3;
		if (i > 0 && s[i - 1] == s[i]) add = 0;
		if (i > 0 && s[i] != s[i - 1]) all_same = false;
	}
	if (all_same) return puts("1"), 0;
	if (n < 4) {
		gen_all();
		return 0;
	}
	dp[0][0] = 1, dp2[1][0][0] = dp2[1][1][1] = dp2[1][2][2] = 1;
	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j < 3; ++j) {
			for (int k = 0; k < 3; ++k) {
				dp[i][j] = (dp[i][j] + dp[i - 1][(j - k + 3) % 3]) % mod;
				if (i == 1) continue;
				for (int l = 0; l < 3; ++l) {
					if (l == k) continue;
					dp2[i][j][k] = (dp2[i][j][k] + dp2[i - 1][(j - k + 3) % 3][l]) % mod;
				}
			}
		}
	}
	int ans = dp[n][m];
	for (int i = 0; i < 3; ++i) {
		ans = (ans - dp2[n][m][i] + mod) % mod;
	}
	cout << (ans + add) % mod << "\n";
	return 0;
}
### 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 <bits/stdc++.h>

using namespace std;

#define SZ(x) ((int)x.size())

const int N = (int)2e5+5;
const int mod = 998244353;
int n, m, dp[N][3], dp2[N][3][3];
string s;

char change(char x, char y) {
	if ((x == 'a' && y == 'b') || (x == 'b' && y == 'a')) return 'c';
	if ((x == 'c' && y == 'b') || (x == 'b' && y == 'c')) return 'a';
	return 'b';
}

void gen_all() {
	map<string, bool> vis;
	queue<string> q;
	q.push(s);
	vis[s] = true;
	while (SZ(q)) {
		string u = q.front(); q.pop();
		for (int i = 0; i < n - 1; ++i) {
			if (u[i] == u[i + 1]) continue;
			string v = "";
			v.assign(u);
			char now = change(v[i], v[i + 1]);
			v[i] = now, v[i + 1] = now;
			if (vis[v]) continue;
			vis[v] = true;
			q.push(v);
		}
	}
	cout << SZ(vis) << "\n";
}

int main() {
	cin >> s;
	n = SZ(s);
	int add = 1;
	bool all_same = true;
	for (int i = 0; i < n; ++i) {
		m = (m + s[i] - 'a') % 3;
		if (i > 0 && s[i - 1] == s[i]) add = 0;
		if (i > 0 && s[i] != s[i - 1]) all_same = false;
	}
	if (all_same) return puts("1"), 0;
	if (n < 4) {
		gen_all();
		return 0;
	}
	dp[0][0] = 1, dp2[1][0][0] = dp2[1][1][1] = dp2[1][2][2] = 1;
	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j < 3; ++j) {
			for (int k = 0; k < 3; ++k) {
				dp[i][j] = (dp[i][j] + dp[i - 1][(j - k + 3) % 3]) % mod;
				if (i == 1) continue;
				for (int l = 0; l < 3; ++l) {
					if (l == k) continue;
					dp2[i][j][k] = (dp2[i][j][k] + dp2[i - 1][(j - k + 3) % 3][l]) % mod;
				}
			}
		}
	}
	int ans = dp[n][m];
	for (int i = 0; i < 3; ++i) {
		ans = (ans - dp2[n][m][i] + mod) % mod;
	}
	cout << (ans + add) % mod << "\n";
	return 0;
}
```