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

#define rep(i, N) for (int i = 0; i < N; i++)
#define pb push_back

typedef long long ll;
const int MOD = 998244353;

void dfs(string s, set<string>& st) {
	if (st.count(s)) return;
	st.insert(s);
	int N = s.length();
	rep(i, N - 1) if (s[i] != s[i + 1]) {
		string t = s;
		t[i] = t[i + 1] = 'a' + 'b' + 'c' - s[i] - s[i + 1];
		dfs(t, st);
	}
}

int f(string s) {
	set<string> st;
	dfs(s, st);
	return st.size();
}

int solve(string s) {
	int N = s.length();
	bool same = true, diff = true;
	rep(i, N - 1) {
		if (s[i] != s[i + 1]) same = false;
		else diff = false;
	}
	if (same) return 1;
	int ans = 1;
	rep(i, N - 1) ans = (ll)ans * 3 % MOD;
	int unko = 0;
	rep(i, N) unko = (unko + s[i] - 'a') % 3;
	vector<vector<int>> dp(3, vector<int>(3));
	dp[0][0] = dp[1][1] = dp[2][2] = 1;
	rep(i, N - 1) {
		vector<vector<int>> _dp(3, vector<int>(3));
		rep(x, 3) rep(y, 3) rep(z, 3) if (x != z)
			_dp[z][(y + z) % 3] = (_dp[z][(y + z) % 3] + dp[x][y]) % MOD;
		dp = _dp;
	}
	rep(x, 3) ans = (ans - dp[x][unko]) % MOD;
	if (diff) ans = (ans + 1) % MOD;
	return (ans + MOD) % MOD;
}

int main() {
	/*
	for (;;) {
		string s; cin >> s;
		cout << f(s) << ' ' << solve(s) << endl;
	}
	*/
	string s; cin >> s;
	if (s.length() <= 3) {
		cout << f(s) << endl;
		return 0;
	}
	cout << solve(s) << endl;
}

### 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 rep(i, N) for (int i = 0; i < N; i++)
#define pb push_back

typedef long long ll;
const int MOD = 998244353;

void dfs(string s, set<string>& st) {
	if (st.count(s)) return;
	st.insert(s);
	int N = s.length();
	rep(i, N - 1) if (s[i] != s[i + 1]) {
		string t = s;
		t[i] = t[i + 1] = 'a' + 'b' + 'c' - s[i] - s[i + 1];
		dfs(t, st);
	}
}

int f(string s) {
	set<string> st;
	dfs(s, st);
	return st.size();
}

int solve(string s) {
	int N = s.length();
	bool same = true, diff = true;
	rep(i, N - 1) {
		if (s[i] != s[i + 1]) same = false;
		else diff = false;
	}
	if (same) return 1;
	int ans = 1;
	rep(i, N - 1) ans = (ll)ans * 3 % MOD;
	int unko = 0;
	rep(i, N) unko = (unko + s[i] - 'a') % 3;
	vector<vector<int>> dp(3, vector<int>(3));
	dp[0][0] = dp[1][1] = dp[2][2] = 1;
	rep(i, N - 1) {
		vector<vector<int>> _dp(3, vector<int>(3));
		rep(x, 3) rep(y, 3) rep(z, 3) if (x != z)
			_dp[z][(y + z) % 3] = (_dp[z][(y + z) % 3] + dp[x][y]) % MOD;
		dp = _dp;
	}
	rep(x, 3) ans = (ans - dp[x][unko]) % MOD;
	if (diff) ans = (ans + 1) % MOD;
	return (ans + MOD) % MOD;
}

int main() {
	/*
	for (;;) {
		string s; cin >> s;
		cout << f(s) << ' ' << solve(s) << endl;
	}
	*/
	string s; cin >> s;
	if (s.length() <= 3) {
		cout << f(s) << endl;
		return 0;
	}
	cout << solve(s) << endl;
}

```