#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cassert>
#include <time.h>
#define int long long
#define endl '\n'
#define INF 1000000000000000000
#define EPS 1e-10
#define all(a) a.begin(),a.end()
#define rep(i, n) for (int i = 0; i < (n); i++)
#define fi first
#define se second
#define pb push_back
#define double long double
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<ll, P> PP;
template<class T, class S> bool chmax(T &a, const S &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T, class S> bool chmin(T &a, const S &b) { if (a > b) { a = b; return 1; } return 0; }
ll gcd(ll n, ll m) { return (m ? gcd(m, n%m) : n); }
ll lcm(ll n, ll m) { return n / gcd(n, m)*m; }

ll mod = 998244353;
int dp[200010][3][3][2];

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(20);
	//modcalc();

	string s;
	cin >> s;
	int n = s.size();
	int ans = 0;
	bool allsame = true;
	bool notsame = true;
	rep(i, n - 1) {
		if (s[i] == s[i + 1]) notsame = false;
		else allsame = false;
	}
	if (allsame) {
		cout << 1 << endl;
		return 0;
	}
	if (n == 2) {
		cout << 2 << endl;
		return 0;
	}
	if (n == 3) {
		if (notsame) {
			if (s[0] != s[2]) cout << 3 << endl;
			else cout << 7 << endl;
		}
		else {
			cout << 6 << endl;
		}
		return 0;
	}
	if (n >= 4) {
		if (notsame) ans++;
		dp[0][0][0][0] = 1;
		dp[0][1][1][0] = 1;
		dp[0][2][2][0] = 1;
		for (int i = 1; i < n; i++) {
			for (int j = 0; j < 3; j++) {
				for (int k = 0; k < 3; k++) {
					for (int l = 0; l < 3; l++) {
						if (k == l) {
							dp[i][(j + l) % 3][l][1] += dp[i - 1][j][k][0] + dp[i - 1][j][k][1];
							dp[i][(j + l) % 3][l][1] %= mod;
						}
						else {
							for (int m = 0; m < 2; m++) {
								dp[i][(j + l) % 3][l][m] += dp[i - 1][j][k][m];
								dp[i][(j + l) % 3][l][m] %= mod;
							}
						}
					}
				}
			}
		}
		int p = 0;
		rep(i, n) {
			int pl = s[i] - 'a';
			p += pl; p %= 3;
		}
		for (int k = 0; k < 3; k++) {
			ans += dp[n - 1][p][k][1];
			ans %= mod;
		}
		cout << ans << endl;
	}
}
### Prompt

Please create a solution in CPP 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 <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cassert>
#include <time.h>
#define int long long
#define endl '\n'
#define INF 1000000000000000000
#define EPS 1e-10
#define all(a) a.begin(),a.end()
#define rep(i, n) for (int i = 0; i < (n); i++)
#define fi first
#define se second
#define pb push_back
#define double long double
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<ll, P> PP;
template<class T, class S> bool chmax(T &a, const S &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T, class S> bool chmin(T &a, const S &b) { if (a > b) { a = b; return 1; } return 0; }
ll gcd(ll n, ll m) { return (m ? gcd(m, n%m) : n); }
ll lcm(ll n, ll m) { return n / gcd(n, m)*m; }

ll mod = 998244353;
int dp[200010][3][3][2];

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(20);
	//modcalc();

	string s;
	cin >> s;
	int n = s.size();
	int ans = 0;
	bool allsame = true;
	bool notsame = true;
	rep(i, n - 1) {
		if (s[i] == s[i + 1]) notsame = false;
		else allsame = false;
	}
	if (allsame) {
		cout << 1 << endl;
		return 0;
	}
	if (n == 2) {
		cout << 2 << endl;
		return 0;
	}
	if (n == 3) {
		if (notsame) {
			if (s[0] != s[2]) cout << 3 << endl;
			else cout << 7 << endl;
		}
		else {
			cout << 6 << endl;
		}
		return 0;
	}
	if (n >= 4) {
		if (notsame) ans++;
		dp[0][0][0][0] = 1;
		dp[0][1][1][0] = 1;
		dp[0][2][2][0] = 1;
		for (int i = 1; i < n; i++) {
			for (int j = 0; j < 3; j++) {
				for (int k = 0; k < 3; k++) {
					for (int l = 0; l < 3; l++) {
						if (k == l) {
							dp[i][(j + l) % 3][l][1] += dp[i - 1][j][k][0] + dp[i - 1][j][k][1];
							dp[i][(j + l) % 3][l][1] %= mod;
						}
						else {
							for (int m = 0; m < 2; m++) {
								dp[i][(j + l) % 3][l][m] += dp[i - 1][j][k][m];
								dp[i][(j + l) % 3][l][m] %= mod;
							}
						}
					}
				}
			}
		}
		int p = 0;
		rep(i, n) {
			int pl = s[i] - 'a';
			p += pl; p %= 3;
		}
		for (int k = 0; k < 3; k++) {
			ans += dp[n - 1][p][k][1];
			ans %= mod;
		}
		cout << ans << endl;
	}
}
```