#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = 998244353;
const ll INF = 1LL << 60;
const double PI = 3.141592653589793238;
const double EPS = 1e-10;
set<string> vis;
ll dp[200001][3][3][2];
void brute(string S) {
	vis.insert(S);
	for (int i = 0; i + 1 < S.size(); i++) {
		if (S[i] == S[i + 1]) continue;
		string T = S;
		T[i] = T[i + 1] = 3 - S[i] - S[i + 1];
		if (vis.find(T) == vis.end()) {
			vis.insert(T);
			brute(T);
		}
	}
}
int main() {
	string S;
	cin >> S;
	int m = 0;
	for (int i = 0; i < S.size(); i++) {
		S[i] -= 'a';
		(m += S[i]) %= 3;
	}
	bool dif = 0, same = 0;
	for (int i = 1; i < S.size(); i++) {
		if (S[i] != S[i - 1]) dif = 1;
		else same = 1;
	}
	if (!dif) {
		cout << 1 << endl;
		return 0;
	}
	if (S.size() <= 3) {
		brute(S);
		cout << vis.size() << endl;
		return 0;
	}
	dp[1][0][0][0] = dp[1][1][1][0] = dp[1][2][2][0] = 1;
	for (int i = 1; i < S.size(); i++) {
		for (int j = 0; j < 3; j++) {
			for (int k = 0; k < 3; k++) {
				for (int l = 0; l < 3; l++) {
					if (k == l) {
						(dp[i + 1][(j + l) % 3][l][1] += dp[i][j][k][0]) %= MOD;
						(dp[i + 1][(j + l) % 3][l][1] += dp[i][j][k][1]) %= MOD;
					}
					else {
						(dp[i + 1][(j + l) % 3][l][0] += dp[i][j][k][0]) %= MOD;
						(dp[i + 1][(j + l) % 3][l][1] += dp[i][j][k][1]) %= MOD;
					}
				}
			}
		}
	}
	ll ans = dp[S.size()][m][0][1];
	(ans += dp[S.size()][m][1][1]) %= MOD;
	(ans += dp[S.size()][m][2][1]) %= MOD;
	if (!same) ans++;
	cout << ans << endl;
}
### 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 MOD = 998244353;
const ll INF = 1LL << 60;
const double PI = 3.141592653589793238;
const double EPS = 1e-10;
set<string> vis;
ll dp[200001][3][3][2];
void brute(string S) {
	vis.insert(S);
	for (int i = 0; i + 1 < S.size(); i++) {
		if (S[i] == S[i + 1]) continue;
		string T = S;
		T[i] = T[i + 1] = 3 - S[i] - S[i + 1];
		if (vis.find(T) == vis.end()) {
			vis.insert(T);
			brute(T);
		}
	}
}
int main() {
	string S;
	cin >> S;
	int m = 0;
	for (int i = 0; i < S.size(); i++) {
		S[i] -= 'a';
		(m += S[i]) %= 3;
	}
	bool dif = 0, same = 0;
	for (int i = 1; i < S.size(); i++) {
		if (S[i] != S[i - 1]) dif = 1;
		else same = 1;
	}
	if (!dif) {
		cout << 1 << endl;
		return 0;
	}
	if (S.size() <= 3) {
		brute(S);
		cout << vis.size() << endl;
		return 0;
	}
	dp[1][0][0][0] = dp[1][1][1][0] = dp[1][2][2][0] = 1;
	for (int i = 1; i < S.size(); i++) {
		for (int j = 0; j < 3; j++) {
			for (int k = 0; k < 3; k++) {
				for (int l = 0; l < 3; l++) {
					if (k == l) {
						(dp[i + 1][(j + l) % 3][l][1] += dp[i][j][k][0]) %= MOD;
						(dp[i + 1][(j + l) % 3][l][1] += dp[i][j][k][1]) %= MOD;
					}
					else {
						(dp[i + 1][(j + l) % 3][l][0] += dp[i][j][k][0]) %= MOD;
						(dp[i + 1][(j + l) % 3][l][1] += dp[i][j][k][1]) %= MOD;
					}
				}
			}
		}
	}
	ll ans = dp[S.size()][m][0][1];
	(ans += dp[S.size()][m][1][1]) %= MOD;
	(ans += dp[S.size()][m][2][1]) %= MOD;
	if (!same) ans++;
	cout << ans << endl;
}
```