#include<bits/stdc++.h>
using namespace std;

long long dp[200001][3][3], mod = 998244353, a = 1, N, sum, th[200001];

// dp[i][j][k] 0~i 和のmod3がj i番目がk 連続あり

int main(){
	string S; cin >> S; N = S.size();
	if(N == 2){
		if(S[0] == S[1]) cout << 1 << endl;
		else cout << 2 << endl;
	}else if(N == 3){
		if(S[0] == S[1] && S[1] == S[2]) cout << 1 << endl;
		else if(S[0] != S[1] && S[1] != S[2] && S[2] != S[0]){
			cout << 3 << endl;
		}else{
			if(S[0] == S[1] || S[1] == S[2]) cout << 6 << endl;
			else cout << 7 << endl;
		}
	}else{
		int c = 1;
		for(int i=0; i<N-1; i++){
			if(S[i] != S[i+1]) c = 0;
		}
		if(c){
			cout << 1 << endl;
			return 0;
		}
		for(int i=0; i<N; i++){
			if(S[i] == 'b') sum = (sum + 1) % 3;
			if(S[i] == 'c') sum = (sum + 2) % 3;
		}
		th[0] = 1;
		for(int i=1; i<=N; i++) th[i] = th[i-1] * 3 % mod;
		dp[1][0][0] = 1, dp[1][1][2] = 1, dp[1][2][1] = 1;
		for(int i=2; 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][k] = (dp[i][j][k] + dp[i-1][(j-k+3)%3][l]) % mod;
						}else{
							dp[i][j][k] = (dp[i][j][k] + th[i-2]) % mod;
						}
					}
				}
			}
		}
		int f = 1;
		for(int i=0; i<N-1; i++){
			if(S[i] == S[i+1]) f = 0;
		}
		cout << (dp[N-1][sum][0] + dp[N-1][sum][1] + dp[N-1][sum][2] + f) % mod << endl;
	}
	return 0;
}

### Prompt

Generate 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;

long long dp[200001][3][3], mod = 998244353, a = 1, N, sum, th[200001];

// dp[i][j][k] 0~i 和のmod3がj i番目がk 連続あり

int main(){
	string S; cin >> S; N = S.size();
	if(N == 2){
		if(S[0] == S[1]) cout << 1 << endl;
		else cout << 2 << endl;
	}else if(N == 3){
		if(S[0] == S[1] && S[1] == S[2]) cout << 1 << endl;
		else if(S[0] != S[1] && S[1] != S[2] && S[2] != S[0]){
			cout << 3 << endl;
		}else{
			if(S[0] == S[1] || S[1] == S[2]) cout << 6 << endl;
			else cout << 7 << endl;
		}
	}else{
		int c = 1;
		for(int i=0; i<N-1; i++){
			if(S[i] != S[i+1]) c = 0;
		}
		if(c){
			cout << 1 << endl;
			return 0;
		}
		for(int i=0; i<N; i++){
			if(S[i] == 'b') sum = (sum + 1) % 3;
			if(S[i] == 'c') sum = (sum + 2) % 3;
		}
		th[0] = 1;
		for(int i=1; i<=N; i++) th[i] = th[i-1] * 3 % mod;
		dp[1][0][0] = 1, dp[1][1][2] = 1, dp[1][2][1] = 1;
		for(int i=2; 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][k] = (dp[i][j][k] + dp[i-1][(j-k+3)%3][l]) % mod;
						}else{
							dp[i][j][k] = (dp[i][j][k] + th[i-2]) % mod;
						}
					}
				}
			}
		}
		int f = 1;
		for(int i=0; i<N-1; i++){
			if(S[i] == S[i+1]) f = 0;
		}
		cout << (dp[N-1][sum][0] + dp[N-1][sum][1] + dp[N-1][sum][2] + f) % mod << endl;
	}
	return 0;
}

```