#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; (i) < (int) (n); (i) ++)
using namespace std;

const long long MOD = 998244353;

int main() {
	string s;
	cin >> s;
	int n = (int) s.size();
	vector<int> a(n);
	bool same = true;
	rep(i, n) { 
		a[i] = (s[i] == 'a' ? 0 : s[i] == 'b' ? 1 : 2);
		if (i) same = same && a[i] == a[i - 1];
	}
	if (same) {
		printf("1\n");
		return 0;
	} else if (n >= 6) {
		int m = 0;
		bool cons = false;
		rep(i, n) {
			m += a[i];
			if (i && a[i - 1] == a[i]) {
				cons = true;
			}
		}
		m %= 3;
		vector<vector<long long>> cur1(3, vector<long long> (3)); // ans = \sum cur1[i][m]
		vector<vector<long long>> cur2(3, vector<long long> (3));
		rep(i, 3) cur2[i][i] = 1;
		rep(i, n - 1) {
			vector<vector<long long>> next1(3, vector<long long> (3));
			vector<vector<long long>> next2(3, vector<long long> (3));
			rep(j, 3) {
				rep(k, 3) {
					rep(l, 3) {
						(next1[l][(k + l) % 3] += cur1[j][k]) %= MOD;
						if (j != l) {
							(next2[l][(k + l) % 3] += cur2[j][k]) %= MOD;
						} else {
							(next1[l][(k + l) % 3] += cur2[j][k]) %= MOD;
						}
					}
				}
			}
			cur1.swap(next1);
			cur2.swap(next2);
		}
		long long ans = !cons;
		rep(i, 3) (ans += cur1[i][m]) %= MOD;
		printf("%lld\n", ans);
	} else {
		set<vector<int>> tozan;
		function<void (vector<int>)> dfs = [&](vector<int> hi) {
			if (tozan.count(hi)) return;
			tozan.insert(hi);
			for (int i = 0; i < (int) hi.size() - 1; i ++) {
				int pro0 = hi[i];
				int pro1 = hi[i + 1];
				if (pro0 != pro1) {
					hi[i] = 3 - pro0 - pro1;
					hi[i + 1] = 3 - pro0 - pro1;
					dfs(hi);
					hi[i] = pro0;
					hi[i + 1] = pro1;
				}
			}
		};
		dfs(a);
		printf("%d\n", (int) tozan.size());
	}
}

### 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>
#define rep(i, n) for (int i = 0; (i) < (int) (n); (i) ++)
using namespace std;

const long long MOD = 998244353;

int main() {
	string s;
	cin >> s;
	int n = (int) s.size();
	vector<int> a(n);
	bool same = true;
	rep(i, n) { 
		a[i] = (s[i] == 'a' ? 0 : s[i] == 'b' ? 1 : 2);
		if (i) same = same && a[i] == a[i - 1];
	}
	if (same) {
		printf("1\n");
		return 0;
	} else if (n >= 6) {
		int m = 0;
		bool cons = false;
		rep(i, n) {
			m += a[i];
			if (i && a[i - 1] == a[i]) {
				cons = true;
			}
		}
		m %= 3;
		vector<vector<long long>> cur1(3, vector<long long> (3)); // ans = \sum cur1[i][m]
		vector<vector<long long>> cur2(3, vector<long long> (3));
		rep(i, 3) cur2[i][i] = 1;
		rep(i, n - 1) {
			vector<vector<long long>> next1(3, vector<long long> (3));
			vector<vector<long long>> next2(3, vector<long long> (3));
			rep(j, 3) {
				rep(k, 3) {
					rep(l, 3) {
						(next1[l][(k + l) % 3] += cur1[j][k]) %= MOD;
						if (j != l) {
							(next2[l][(k + l) % 3] += cur2[j][k]) %= MOD;
						} else {
							(next1[l][(k + l) % 3] += cur2[j][k]) %= MOD;
						}
					}
				}
			}
			cur1.swap(next1);
			cur2.swap(next2);
		}
		long long ans = !cons;
		rep(i, 3) (ans += cur1[i][m]) %= MOD;
		printf("%lld\n", ans);
	} else {
		set<vector<int>> tozan;
		function<void (vector<int>)> dfs = [&](vector<int> hi) {
			if (tozan.count(hi)) return;
			tozan.insert(hi);
			for (int i = 0; i < (int) hi.size() - 1; i ++) {
				int pro0 = hi[i];
				int pro1 = hi[i + 1];
				if (pro0 != pro1) {
					hi[i] = 3 - pro0 - pro1;
					hi[i + 1] = 3 - pro0 - pro1;
					dfs(hi);
					hi[i] = pro0;
					hi[i + 1] = pro1;
				}
			}
		};
		dfs(a);
		printf("%d\n", (int) tozan.size());
	}
}

```