#include <bits/stdc++.h>
typedef long long ll;
const ll P = 998244353;
const int N = 2e5 + 5;
inline void up(int &x, int y) { x < y ? x = y : 0; }
inline void down(int &x, int y) { x > y ? x = y : 0; }
inline int max(const int x, const int y) { return x > y ? x : y; }
inline int min(const int x, const int y) { return x < y ? x : y; }

inline void mod(ll &x) { x >= P ? x -= P : x; }

std::string str;
std::set < std::string > s;
int n;
ll dp[N][3][3][2];
inline bool all_equal(std::string str) {
	for (int i = 0; i < n; ++i)
		if (str[i] != str[0]) return false;
	return true;
}
inline void bfs(std::string str) {
	if (s.count(str)) return;
	s.insert(str);
	for (int i = 0; i < n - 1; ++i) 
		if (str[i] != str[i + 1]) {
		std::string t = str;
		if (str[i] != 'a' && str[i + 1] != 'a') t[i] = t[i + 1] = 'a';
		if (str[i] != 'b' && str[i + 1] != 'b') t[i] = t[i + 1] = 'b';
		if (str[i] != 'c' && str[i + 1] != 'c') t[i] = t[i + 1] = 'c';
		bfs(t);
	}
} 

inline ll dp_solve() {
	int s1 = 0;
	for (int i = 0; i < n; ++i) s1 += str[i] - 'a';
	s1 %= 3;
	for (int i = 0; i < 3; ++i) dp[0][i][i][0] = 1;
	for (int i = 0; i < n - 1; ++i)
		for (int s0 = 0; s0 < 3; ++s0)
			for (int now = 0; now < 3; ++now)
				for (int type = 0; type <= 1; ++type)
					for (int nxt = 0; nxt < 3; ++nxt) 
						mod(dp[i + 1][(s0 + nxt) % 3][nxt][type | (now == nxt)] += dp[i][s0][now][type]);
	ll ans = 0;
	for (int i = 0; i < 3; ++i) mod(ans += dp[n - 1][s1][i][1]);
	int ok = 0;
	for (int i = 1; i < n; ++i)
		if (str[i] == str[i - 1]) ok = 1;
	if (! ok) mod(ans += 1);
	return ans; 
}
int main() {
    std::ios::sync_with_stdio(false), std::cin.tie(0);
    std::cin >> str;
    n = str.size();
    if (all_equal(str)) return std::cout << 1 << '\n', 0;
    if (n < 4) bfs(str), std::cout << s.size() << '\n';
    else std::cout << dp_solve() << '\n';
	return 0;
}
### Prompt

Please provide a cpp coded solution 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>
typedef long long ll;
const ll P = 998244353;
const int N = 2e5 + 5;
inline void up(int &x, int y) { x < y ? x = y : 0; }
inline void down(int &x, int y) { x > y ? x = y : 0; }
inline int max(const int x, const int y) { return x > y ? x : y; }
inline int min(const int x, const int y) { return x < y ? x : y; }

inline void mod(ll &x) { x >= P ? x -= P : x; }

std::string str;
std::set < std::string > s;
int n;
ll dp[N][3][3][2];
inline bool all_equal(std::string str) {
	for (int i = 0; i < n; ++i)
		if (str[i] != str[0]) return false;
	return true;
}
inline void bfs(std::string str) {
	if (s.count(str)) return;
	s.insert(str);
	for (int i = 0; i < n - 1; ++i) 
		if (str[i] != str[i + 1]) {
		std::string t = str;
		if (str[i] != 'a' && str[i + 1] != 'a') t[i] = t[i + 1] = 'a';
		if (str[i] != 'b' && str[i + 1] != 'b') t[i] = t[i + 1] = 'b';
		if (str[i] != 'c' && str[i + 1] != 'c') t[i] = t[i + 1] = 'c';
		bfs(t);
	}
} 

inline ll dp_solve() {
	int s1 = 0;
	for (int i = 0; i < n; ++i) s1 += str[i] - 'a';
	s1 %= 3;
	for (int i = 0; i < 3; ++i) dp[0][i][i][0] = 1;
	for (int i = 0; i < n - 1; ++i)
		for (int s0 = 0; s0 < 3; ++s0)
			for (int now = 0; now < 3; ++now)
				for (int type = 0; type <= 1; ++type)
					for (int nxt = 0; nxt < 3; ++nxt) 
						mod(dp[i + 1][(s0 + nxt) % 3][nxt][type | (now == nxt)] += dp[i][s0][now][type]);
	ll ans = 0;
	for (int i = 0; i < 3; ++i) mod(ans += dp[n - 1][s1][i][1]);
	int ok = 0;
	for (int i = 1; i < n; ++i)
		if (str[i] == str[i - 1]) ok = 1;
	if (! ok) mod(ans += 1);
	return ans; 
}
int main() {
    std::ios::sync_with_stdio(false), std::cin.tie(0);
    std::cin >> str;
    n = str.size();
    if (all_equal(str)) return std::cout << 1 << '\n', 0;
    if (n < 4) bfs(str), std::cout << s.size() << '\n';
    else std::cout << dp_solve() << '\n';
	return 0;
}
```