#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
int f(string str) {
	set < string > s;
	s.insert(str);
    while (1) {
    	int ok = 0;
    	for (auto it : s) {
    		for (int i = 0;i + 1 < it.length();++i) {
    			if (it[i] != it[i + 1]) {
    				string ss = it;
    				for (char c = 'a';c <= 'c';++c)
    					if (ss[i] != c && ss[i + 1] != c) {
    						ss[i] = ss[i + 1] = c;
    						break;
    					}
    				if (!s.count(ss))
    					ok = 1;
    				s.insert(ss);
    			}
    		}
    	}
    	if (!ok)
    		break;
    }
    return s.size();
}
const int N = 5e5;
int dp[N][3][3][2];
const int mod = 998244353;
void add(int & x,int y) {
	x = (x + y) % mod;
}
int main(void)
{
	string str;
	cin>>str;
	if (str.length() <= 3)
		cout << f(str) << '\n';
	else {
		int ok = 1;
		for (auto it : str)
			ok &= it == str[0];
		if (ok) {
			cout << "1\n";
			return 0;
		}
		int sum = 0;
		for (auto it : str)
			sum += (it - '0');
		sum %= 3;
		for (int i = 0;i < 3;++i)
			dp[1][i][i][0] = 1;
		int n = str.length();
		for (int i = 1;i < n;++i)
			for (int prev = 0;prev < 3;++prev)
				for (int sm = 0;sm < 3;++sm)
					for (int nw = 0;nw < 3;++nw)
						for (int eq = 0;eq < 2;++eq)
							add(dp[i + 1][nw][(sm + nw) % 3][eq | (nw == prev)],dp[i][prev][sm][eq]);
		int ans = 0;
		for (int t = 0;t < 3;++t)
			add(ans,dp[n][t][sum][1]);
		int cnt = 1;
		for (int i = 0;i + 1 < n;++i)
			cnt &= str[i] != str[i + 1];
		(ans += cnt) %= mod;
		cout << ans << '\n';
	}
    return 0;
}
### 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;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
int f(string str) {
	set < string > s;
	s.insert(str);
    while (1) {
    	int ok = 0;
    	for (auto it : s) {
    		for (int i = 0;i + 1 < it.length();++i) {
    			if (it[i] != it[i + 1]) {
    				string ss = it;
    				for (char c = 'a';c <= 'c';++c)
    					if (ss[i] != c && ss[i + 1] != c) {
    						ss[i] = ss[i + 1] = c;
    						break;
    					}
    				if (!s.count(ss))
    					ok = 1;
    				s.insert(ss);
    			}
    		}
    	}
    	if (!ok)
    		break;
    }
    return s.size();
}
const int N = 5e5;
int dp[N][3][3][2];
const int mod = 998244353;
void add(int & x,int y) {
	x = (x + y) % mod;
}
int main(void)
{
	string str;
	cin>>str;
	if (str.length() <= 3)
		cout << f(str) << '\n';
	else {
		int ok = 1;
		for (auto it : str)
			ok &= it == str[0];
		if (ok) {
			cout << "1\n";
			return 0;
		}
		int sum = 0;
		for (auto it : str)
			sum += (it - '0');
		sum %= 3;
		for (int i = 0;i < 3;++i)
			dp[1][i][i][0] = 1;
		int n = str.length();
		for (int i = 1;i < n;++i)
			for (int prev = 0;prev < 3;++prev)
				for (int sm = 0;sm < 3;++sm)
					for (int nw = 0;nw < 3;++nw)
						for (int eq = 0;eq < 2;++eq)
							add(dp[i + 1][nw][(sm + nw) % 3][eq | (nw == prev)],dp[i][prev][sm][eq]);
		int ans = 0;
		for (int t = 0;t < 3;++t)
			add(ans,dp[n][t][sum][1]);
		int cnt = 1;
		for (int i = 0;i + 1 < n;++i)
			cnt &= str[i] != str[i + 1];
		(ans += cnt) %= mod;
		cout << ans << '\n';
	}
    return 0;
}
```