#include <iostream>
#include <string>
#define llint long long
#define mod 998244353

using namespace std;

string s;
llint dp[200005][3][4];

int main(void)
{
	cin >> s;
	
	bool flag = true;
	for(int i = 0; i < s.size(); i++){
		if(s[i] != s[0]){
			flag = false;
			break;
		}
	}
	if(flag){
		cout << 1 << endl;
		return 0;
	}
	if(s.size() <= 2){
		cout << 2 << endl;
		return 0;
	}
	
	llint sum = 0;
	for(int i = 0; i < s.size(); i++){
		if(s[i] == 'b') sum++;
		if(s[i] == 'c') sum+= 2;
	}
	sum %= 3;
	if(sum == 0 && s.size() == 3){
		cout << 3 << endl;
		return 0;
	}
	
	llint ans = 0; flag = false;
	for(int i = 1; i < s.size(); i++){
		if(s[i-1] == s[i]){
			flag = true;
			break;
		}
	}
	if(!flag) ans++;
	
	dp[0][0][0] = 1;
	for(int i = 0; i < s.size(); i++){
		for(int j = 0; j < 3; j++){
			for(int k = 0; k < 4; k++){
				for(int l = 0; l < 3; l++){
					int kk = l;
					if(k == 3 || (i != 0 && k == l)) kk = 3;
					dp[i+1][(j+l)%3][kk] += dp[i][j][k];
					dp[i+1][(j+l)%3][kk] %= mod;
				}
			}
		}
	}
	
	ans += dp[s.size()][sum][3];
	cout << ans << endl;
	return 0;
}
### 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 <string>
#define llint long long
#define mod 998244353

using namespace std;

string s;
llint dp[200005][3][4];

int main(void)
{
	cin >> s;
	
	bool flag = true;
	for(int i = 0; i < s.size(); i++){
		if(s[i] != s[0]){
			flag = false;
			break;
		}
	}
	if(flag){
		cout << 1 << endl;
		return 0;
	}
	if(s.size() <= 2){
		cout << 2 << endl;
		return 0;
	}
	
	llint sum = 0;
	for(int i = 0; i < s.size(); i++){
		if(s[i] == 'b') sum++;
		if(s[i] == 'c') sum+= 2;
	}
	sum %= 3;
	if(sum == 0 && s.size() == 3){
		cout << 3 << endl;
		return 0;
	}
	
	llint ans = 0; flag = false;
	for(int i = 1; i < s.size(); i++){
		if(s[i-1] == s[i]){
			flag = true;
			break;
		}
	}
	if(!flag) ans++;
	
	dp[0][0][0] = 1;
	for(int i = 0; i < s.size(); i++){
		for(int j = 0; j < 3; j++){
			for(int k = 0; k < 4; k++){
				for(int l = 0; l < 3; l++){
					int kk = l;
					if(k == 3 || (i != 0 && k == l)) kk = 3;
					dp[i+1][(j+l)%3][kk] += dp[i][j][k];
					dp[i+1][(j+l)%3][kk] %= mod;
				}
			}
		}
	}
	
	ans += dp[s.size()][sum][3];
	cout << ans << endl;
	return 0;
}
```