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

int n;
map <string, bool> mp;

void brute(string &s) {
	if (mp.find(s) != mp.end()) return;
	mp[s] = true;

	for (int i = 0; i < n - 1; ++i) {
		if (s[i] != s[i + 1]) {
			int a = s[i] - '0';
			int b = s[i + 1] - '0';
			int c;
			for (c = 0; c < 3; ++c) {
				if ((c + c) % 3 == (a + b) % 3) break;
			}
			string nw = s;
			nw[i] = (char)(c + '0');
			nw[i + 1] = (char)(c + '0');
			brute(nw);
		}
	}
}
// --------------------------------------------------

const int N = 200005;
const int mod = 998244353;

int dp[N][3][3][2];

void add(int &x, int y) {
	x += y;
	while(x >= mod) x -= mod;
	while(x < 0) x += mod;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);

	string s; cin >> s;
	n = s.size();
	for (int i = 0; i < n; ++i) {
		s[i] = s[i] - 'a' + '0';
	}

	// corner cases
	if (n <= 3) {
		brute(s);
		cout << mp.size() << endl;
		return 0;
	}
	bool equal_all = true;
	for (int i = 0; i < n; ++i) {
		equal_all &= (s[i] == s[0]);
	}
	if (equal_all) {
		cout << 1 << endl;
		return 0;
	}

	// dp
	int t = 0;
	bool adj = false;
	for (int i = 0; i < n; ++i) {
		t = (t + s[i] - '0') % 3;
		if (i > 0) adj |= (s[i] == s[i - 1]);
	}

	dp[0][0][0][0] = 1; // dp[pos][mod3][last][any_equal_adjacent_pairs?]
	for (int i = 0; i < n; ++i) {
		for (int sum = 0; sum < 3; ++sum) {
			for (int last = 0; last < 3; ++last) {
				for (int have = 0; have < 2; ++have) {
					if (!dp[i][sum][last][have]) continue;

					for (int nxt = 0; nxt < 3; ++nxt) {
						bool new_have = have;
						if (i != 0 && nxt == last) new_have = 1;
						add(dp[i + 1][(sum + nxt) % 3][nxt][new_have], dp[i][sum][last][have]);
					}
				}
			}
		}
	}

	int res = 1; // s itself
	for (int last = 0; last < 3; ++last) {
		add(res, dp[n][t][last][1]);
	}

	if (adj) add(res, -1); // s is repeatly computed

	cout << res << endl;
}
### Prompt

Please formulate 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;

int n;
map <string, bool> mp;

void brute(string &s) {
	if (mp.find(s) != mp.end()) return;
	mp[s] = true;

	for (int i = 0; i < n - 1; ++i) {
		if (s[i] != s[i + 1]) {
			int a = s[i] - '0';
			int b = s[i + 1] - '0';
			int c;
			for (c = 0; c < 3; ++c) {
				if ((c + c) % 3 == (a + b) % 3) break;
			}
			string nw = s;
			nw[i] = (char)(c + '0');
			nw[i + 1] = (char)(c + '0');
			brute(nw);
		}
	}
}
// --------------------------------------------------

const int N = 200005;
const int mod = 998244353;

int dp[N][3][3][2];

void add(int &x, int y) {
	x += y;
	while(x >= mod) x -= mod;
	while(x < 0) x += mod;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);

	string s; cin >> s;
	n = s.size();
	for (int i = 0; i < n; ++i) {
		s[i] = s[i] - 'a' + '0';
	}

	// corner cases
	if (n <= 3) {
		brute(s);
		cout << mp.size() << endl;
		return 0;
	}
	bool equal_all = true;
	for (int i = 0; i < n; ++i) {
		equal_all &= (s[i] == s[0]);
	}
	if (equal_all) {
		cout << 1 << endl;
		return 0;
	}

	// dp
	int t = 0;
	bool adj = false;
	for (int i = 0; i < n; ++i) {
		t = (t + s[i] - '0') % 3;
		if (i > 0) adj |= (s[i] == s[i - 1]);
	}

	dp[0][0][0][0] = 1; // dp[pos][mod3][last][any_equal_adjacent_pairs?]
	for (int i = 0; i < n; ++i) {
		for (int sum = 0; sum < 3; ++sum) {
			for (int last = 0; last < 3; ++last) {
				for (int have = 0; have < 2; ++have) {
					if (!dp[i][sum][last][have]) continue;

					for (int nxt = 0; nxt < 3; ++nxt) {
						bool new_have = have;
						if (i != 0 && nxt == last) new_have = 1;
						add(dp[i + 1][(sum + nxt) % 3][nxt][new_have], dp[i][sum][last][have]);
					}
				}
			}
		}
	}

	int res = 1; // s itself
	for (int last = 0; last < 3; ++last) {
		add(res, dp[n][t][last][1]);
	}

	if (adj) add(res, -1); // s is repeatly computed

	cout << res << endl;
}
```