#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

long long int DP[100000][3][3] = {};
long long int INF = 998244353;

long long int pow(int n, int m){
	long long int ret = 1;
	for(int i = 0; i < m; i++){
		ret *= n;
		ret %= INF;
	}
	return ret;
}

int main() {
	
	string str;
	cin >> str;
	long long int ans = 0;
	bool flag = true;
	for(int i = 0; i < str.size() - 1; i++){
		if(str[i] != str[i + 1]){
			flag = false;
		}
	}
	if(flag){
		cout << "1" << endl;
		return 0;
	}
	if(str.size() == 3){
		if(str[0] != str[1] && str[2] != str[1] && str[0] != str[2]){
			cout << "3" << endl;
		}else if(str[0] == str[2]){
			cout << "7" << endl;
		}else{
			cout << "6" << endl;
		}
		return 0;
	}
	if(str.size() % 3 != 0){
		
		bool flag = true;
		for(int i = 0; i < str.size() - 1; i++){
			if(str[i] == str[i + 1]){
				flag = false;
			}
		}
		
		ans = pow(3, str.size() - 1);
		
		ans -= pow(2, str.size() - 1);
		
		if(flag){
			ans++;
		}
		
	}else{
		DP[1][0][0] = 2;
		DP[1][1][0] = 2;
		DP[1][2][0] = 2;
		DP[1][0][1] = 1;
		DP[1][1][1] = 1;
		DP[1][2][1] = 1;
		DP[1][0][2] = 1;
		DP[1][1][2] = 1;
		DP[1][2][2] = 1;
		for(int i = 1; i < str.size() / 3; i++){
			for(int j = 0; j < 3; j++){
				for(int k = 0; k < 3; k++){
					DP[i + 1][j][k] = DP[i][j][k] * 2;
					DP[i + 1][j][k] += DP[i][(j + 1) % 3][k];
					DP[i + 1][j][k] += DP[i][(j + 2) % 3][k];
					DP[i + 1][j][k] += DP[i][(j + 1) % 3][(k + 1) % 3];
					DP[i + 1][j][k] += DP[i][(j + 2) % 3][(k + 1) % 3];
					DP[i + 1][j][k] += DP[i][(j + 1) % 3][(k + 2) % 3];
					DP[i + 1][j][k] += DP[i][(j + 2) % 3][(k + 2) % 3];
					DP[i + 1][j][k] %= INF;
				}
			}
		}
		int rest = 0;
		bool flag = true;
		for(int i = 0; i < str.size() - 1; i++){
			rest += str[i] - 'a';
			if(str[i] == str[i + 1]){
				flag = false;
			}
		}
		rest += str[str.size() - 1] - 'a';
		rest %= 3;
		
		ans = pow(3, str.size() - 1);
		
		ans -= DP[str.size() / 3][0][rest];
		ans -= DP[str.size() / 3][1][rest];
		ans -= DP[str.size() / 3][2][rest];
		
		if(flag){
			ans++;
		}
		
	}
	
	ans += INF * 100;
	ans %= INF;
	
	cout << ans << endl;
	
	return 0;
}

### Prompt

Develop a solution in CPP to the problem described below:

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>
#include <algorithm>
using namespace std;

long long int DP[100000][3][3] = {};
long long int INF = 998244353;

long long int pow(int n, int m){
	long long int ret = 1;
	for(int i = 0; i < m; i++){
		ret *= n;
		ret %= INF;
	}
	return ret;
}

int main() {
	
	string str;
	cin >> str;
	long long int ans = 0;
	bool flag = true;
	for(int i = 0; i < str.size() - 1; i++){
		if(str[i] != str[i + 1]){
			flag = false;
		}
	}
	if(flag){
		cout << "1" << endl;
		return 0;
	}
	if(str.size() == 3){
		if(str[0] != str[1] && str[2] != str[1] && str[0] != str[2]){
			cout << "3" << endl;
		}else if(str[0] == str[2]){
			cout << "7" << endl;
		}else{
			cout << "6" << endl;
		}
		return 0;
	}
	if(str.size() % 3 != 0){
		
		bool flag = true;
		for(int i = 0; i < str.size() - 1; i++){
			if(str[i] == str[i + 1]){
				flag = false;
			}
		}
		
		ans = pow(3, str.size() - 1);
		
		ans -= pow(2, str.size() - 1);
		
		if(flag){
			ans++;
		}
		
	}else{
		DP[1][0][0] = 2;
		DP[1][1][0] = 2;
		DP[1][2][0] = 2;
		DP[1][0][1] = 1;
		DP[1][1][1] = 1;
		DP[1][2][1] = 1;
		DP[1][0][2] = 1;
		DP[1][1][2] = 1;
		DP[1][2][2] = 1;
		for(int i = 1; i < str.size() / 3; i++){
			for(int j = 0; j < 3; j++){
				for(int k = 0; k < 3; k++){
					DP[i + 1][j][k] = DP[i][j][k] * 2;
					DP[i + 1][j][k] += DP[i][(j + 1) % 3][k];
					DP[i + 1][j][k] += DP[i][(j + 2) % 3][k];
					DP[i + 1][j][k] += DP[i][(j + 1) % 3][(k + 1) % 3];
					DP[i + 1][j][k] += DP[i][(j + 2) % 3][(k + 1) % 3];
					DP[i + 1][j][k] += DP[i][(j + 1) % 3][(k + 2) % 3];
					DP[i + 1][j][k] += DP[i][(j + 2) % 3][(k + 2) % 3];
					DP[i + 1][j][k] %= INF;
				}
			}
		}
		int rest = 0;
		bool flag = true;
		for(int i = 0; i < str.size() - 1; i++){
			rest += str[i] - 'a';
			if(str[i] == str[i + 1]){
				flag = false;
			}
		}
		rest += str[str.size() - 1] - 'a';
		rest %= 3;
		
		ans = pow(3, str.size() - 1);
		
		ans -= DP[str.size() / 3][0][rest];
		ans -= DP[str.size() / 3][1][rest];
		ans -= DP[str.size() / 3][2][rest];
		
		if(flag){
			ans++;
		}
		
	}
	
	ans += INF * 100;
	ans %= INF;
	
	cout << ans << endl;
	
	return 0;
}

```