#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <set>
#include <cstring>

using namespace std;

const int MOD = 998244353;

bool sameAll(const string& s){
	for(auto c : s) if(c != s[0]) return false;
	return true;
}

int search(const string& s){
	set<string> S; S.insert(s);
	queue<string> qu; qu.push(s);
	while(!qu.empty()){
		string str = qu.front(); qu.pop();
		for(int i=0;i+1<str.size();i++){
			if(str[i] == str[i+1]) continue;
			char c = 'a' + 3 - (str[i]-'a' + str[i+1]-'a');
			string next = str;
			next[i] = next[i+1] = c;
			if(S.count(next)) continue;
			S.insert(next);
			qu.push(next);
		}
	}
	return S.size();
}

int solve(const string& s){
	if(sameAll(s)) return 1;
	if(s.size() <= 4) return search(s);
	int dp[2][2][3][3];
	memset(dp, 0, sizeof(dp));
	for(int i=0;i<3;i++) dp[0][0][i][i] = 1;
	int type = s[0] - 'a';
	bool hasAdj = false;
	for(int i=1;i<s.size();i++){
		type = (type + s[i] - 'a') % 3;
		if(s[i] == s[i-1]) hasAdj = true;
		memset(dp[1], 0, sizeof(dp[1]));
		for(int adj=0;adj<2;adj++){
			for(int sum=0;sum<3;sum++){
				for(int prev=0;prev<3;prev++){
					for(int next=0;next<3;next++){
						int nextAdj = (adj == 1 || prev == next) ? 1 : 0;
						int nextSum = (sum + next) % 3;
						int& nextVal = dp[1][nextAdj][nextSum][next];
						nextVal = (nextVal + dp[0][adj][sum][prev]) % MOD; 
					}
				}
			}
		}
		memcpy(dp[0], dp[1], sizeof(dp[0]));
	}
	int res = 0;
	for(int i=0;i<3;i++) res = (res + dp[0][1][type][i]) % MOD;
	if(!hasAdj) res = (res + 1) % MOD;
	return res;
}

int main(){
	string S;
	while(cin >> S) cout << solve(S) << endl;
}

### Prompt

Your task is to create 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 <iostream>
#include <vector>
#include <string>
#include <queue>
#include <set>
#include <cstring>

using namespace std;

const int MOD = 998244353;

bool sameAll(const string& s){
	for(auto c : s) if(c != s[0]) return false;
	return true;
}

int search(const string& s){
	set<string> S; S.insert(s);
	queue<string> qu; qu.push(s);
	while(!qu.empty()){
		string str = qu.front(); qu.pop();
		for(int i=0;i+1<str.size();i++){
			if(str[i] == str[i+1]) continue;
			char c = 'a' + 3 - (str[i]-'a' + str[i+1]-'a');
			string next = str;
			next[i] = next[i+1] = c;
			if(S.count(next)) continue;
			S.insert(next);
			qu.push(next);
		}
	}
	return S.size();
}

int solve(const string& s){
	if(sameAll(s)) return 1;
	if(s.size() <= 4) return search(s);
	int dp[2][2][3][3];
	memset(dp, 0, sizeof(dp));
	for(int i=0;i<3;i++) dp[0][0][i][i] = 1;
	int type = s[0] - 'a';
	bool hasAdj = false;
	for(int i=1;i<s.size();i++){
		type = (type + s[i] - 'a') % 3;
		if(s[i] == s[i-1]) hasAdj = true;
		memset(dp[1], 0, sizeof(dp[1]));
		for(int adj=0;adj<2;adj++){
			for(int sum=0;sum<3;sum++){
				for(int prev=0;prev<3;prev++){
					for(int next=0;next<3;next++){
						int nextAdj = (adj == 1 || prev == next) ? 1 : 0;
						int nextSum = (sum + next) % 3;
						int& nextVal = dp[1][nextAdj][nextSum][next];
						nextVal = (nextVal + dp[0][adj][sum][prev]) % MOD; 
					}
				}
			}
		}
		memcpy(dp[0], dp[1], sizeof(dp[0]));
	}
	int res = 0;
	for(int i=0;i<3;i++) res = (res + dp[0][1][type][i]) % MOD;
	if(!hasAdj) res = (res + 1) % MOD;
	return res;
}

int main(){
	string S;
	while(cin >> S) cout << solve(S) << endl;
}

```