#ifndef BZ
#pragma GCC optimize "-O3"
#endif
#include <bits/stdc++.h>

#define FASTIO
#define ALL(v) (v).begin(), (v).end()

#ifdef FASTIO
#define scanf abacaba
#define printf abacaba
#endif

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

using namespace std;

const ll MOD = 998244353;

ll pw(ll a, ll b) {
	ll ans = 1; while (b) {
		while (!(b & 1)) b >>= 1, a = (a * a) % MOD;
		ans = (ans * a) % MOD, --b;
	} return ans;
}

char get(char a, char b) {
	return 'a' ^ 'b' ^ 'c' ^ a ^ b;
}

int main() {
#ifdef BZ
	freopen("in", "r", stdin);
#endif
#ifdef FASTIO
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#endif
	string s;
	cin >> s;
	if (s.size() <= 3) {
		set<string> ss;
		queue<string> qu;
		ss.insert(s);
		qu.push(s);
		while (!qu.empty()) {
			string s = qu.front();
			qu.pop();
			for (int i = 0; i + 1 < s.size(); ++i) {
				if (s[i] != s[i + 1]) {
					string t = s;
					t[i] = t[i + 1] = get(s[i], s[i + 1]);
					if (!ss.count(t))
						ss.insert(t), qu.push(t);
				}
			}
		}
		cout << ss.size() << "\n";
		return 0;
	}
	int fl = 0;
	for (int i = 1; i < s.size(); ++i)
		if (s[i] != s[0])
			fl = 1;
	if (!fl) {
		cout << 1 << "\n";
		return 0;
	}

	ll ans = 0;
	for (int i = 0; i + 2 < s.size(); ++i) {
		ans = (ans + pw(2, i) * pw(3, s.size() - i - 2)) % MOD;
	}
	if (s.size() % 3 == 0) {
		int cnt = s.size() / 3 * 2 - 1;
		int sum = 0;
		for (char c: s)
			sum = (sum + c - 'a') % 3;
		ll cc[3] = {1, 0, 0};
		for (int i = 0; i < cnt; ++i) {
			ll dp[3] = {0, 0, 0};
			for (int j = 0; j < 3; ++j)
				for (int k = 0; k < 3; ++k)
					if (k != j)
						dp[k] = (dp[k] + cc[j]) % MOD;
			copy(dp, dp + 3, cc);
		}
		ans = (ans + cc[sum] * 3 % MOD * pw(2, s.size() / 3 - 1)) % MOD;
	}
	else {
		ans = (ans + pw(2, s.size() - 2)) % MOD;
	}
	fl = 0;
	for (int i = 0; i + 1 < s.size(); ++i)
		if (s[i] == s[i + 1])
			fl = 1;
	if (!fl)
		ans = (ans + 1) % MOD;
	cout << ans << "\n";
	return 0;
}


### Prompt

Generate 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
#ifndef BZ
#pragma GCC optimize "-O3"
#endif
#include <bits/stdc++.h>

#define FASTIO
#define ALL(v) (v).begin(), (v).end()

#ifdef FASTIO
#define scanf abacaba
#define printf abacaba
#endif

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

using namespace std;

const ll MOD = 998244353;

ll pw(ll a, ll b) {
	ll ans = 1; while (b) {
		while (!(b & 1)) b >>= 1, a = (a * a) % MOD;
		ans = (ans * a) % MOD, --b;
	} return ans;
}

char get(char a, char b) {
	return 'a' ^ 'b' ^ 'c' ^ a ^ b;
}

int main() {
#ifdef BZ
	freopen("in", "r", stdin);
#endif
#ifdef FASTIO
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#endif
	string s;
	cin >> s;
	if (s.size() <= 3) {
		set<string> ss;
		queue<string> qu;
		ss.insert(s);
		qu.push(s);
		while (!qu.empty()) {
			string s = qu.front();
			qu.pop();
			for (int i = 0; i + 1 < s.size(); ++i) {
				if (s[i] != s[i + 1]) {
					string t = s;
					t[i] = t[i + 1] = get(s[i], s[i + 1]);
					if (!ss.count(t))
						ss.insert(t), qu.push(t);
				}
			}
		}
		cout << ss.size() << "\n";
		return 0;
	}
	int fl = 0;
	for (int i = 1; i < s.size(); ++i)
		if (s[i] != s[0])
			fl = 1;
	if (!fl) {
		cout << 1 << "\n";
		return 0;
	}

	ll ans = 0;
	for (int i = 0; i + 2 < s.size(); ++i) {
		ans = (ans + pw(2, i) * pw(3, s.size() - i - 2)) % MOD;
	}
	if (s.size() % 3 == 0) {
		int cnt = s.size() / 3 * 2 - 1;
		int sum = 0;
		for (char c: s)
			sum = (sum + c - 'a') % 3;
		ll cc[3] = {1, 0, 0};
		for (int i = 0; i < cnt; ++i) {
			ll dp[3] = {0, 0, 0};
			for (int j = 0; j < 3; ++j)
				for (int k = 0; k < 3; ++k)
					if (k != j)
						dp[k] = (dp[k] + cc[j]) % MOD;
			copy(dp, dp + 3, cc);
		}
		ans = (ans + cc[sum] * 3 % MOD * pw(2, s.size() / 3 - 1)) % MOD;
	}
	else {
		ans = (ans + pw(2, s.size() - 2)) % MOD;
	}
	fl = 0;
	for (int i = 0; i + 1 < s.size(); ++i)
		if (s[i] == s[i + 1])
			fl = 1;
	if (!fl)
		ans = (ans + 1) % MOD;
	cout << ans << "\n";
	return 0;
}


```