#include<bits/stdc++.h>
using namespace std;
#define MOD 998244353
inline int read() {
	char ch = getchar(); int x = 0, f = 1;
	while(ch < '0' || ch > '9') {
		if(ch == '-') f = -1;
		ch = getchar();
	}
	while('0' <= ch && ch <= '9') {
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return x * f;
}
char s[200010];
int f[200010][3][3][2];
set<string> S;
inline void dfs(string st) {
	//cerr << "string " << st << endl;
	int n = st.size();
	for(int i = 0; i + 1 < n; ++ i) {
		if(st[i] == st[i + 1]) continue;
		string en = st;
		char New = 3 - (st[i] - 'a') - (st[i + 1] - 'a') + 'a';
		en[i] = en[i + 1] = New;
		if(S.find(en) == S.end()) {
			S.insert(en);
			dfs(en);
		}
	}
}
inline void solve(int n){
	string st = "";
	for(int i = 1; i <= n; ++ i) {
		st += s[i];
	}
	S.insert(st);
	//cerr << st << endl;
	dfs(st);
	printf("%d\n", S.size());
}
int main() {
	//freopen("a.in", "r", stdin);
	scanf("%s", s + 1);
	int n = strlen(s + 1);
	if(n <= 3) solve(n);
	else {
		int flag = 0;
		for(int i = 1; i < n; ++ i) {
			if(s[i] != s[i + 1]) ++ flag;
		}
		int Sum = 0;
		for(int i = 1; i <= n; ++ i) {
			Sum += s[i] - 'a';
		}
		Sum %= 3;
		if(!flag) {
			return puts("1"), 0;
		}
		f[1][0][0][0] = f[1][1][1][0] = f[1][2][2][0] = 1;
		for(int i = 1; i < n; ++ i) {
			for(int j = 0; j <= 2; ++ j) {
				for(int k = 0; k <= 2; ++ k) {
					for(int w = 0; w <= 1; ++ w) {
						for(int t = 0; t <= 2; ++ t) {
							(f[i + 1][t][(k + t) % 3][w | (t == j)] += f[i][j][k][w]) %= MOD;
						}
					}
				}
			}
		}
		int Ans = 0;
		for(int i = 0; i <= 2; ++ i) {
			Ans += f[n][i][Sum][1];
			Ans %= MOD;
		} 
		if(flag == n - 1) (++ Ans) %= MOD;
		printf("%d\n", Ans);
	}
} 
### Prompt

Create a solution in Cpp for 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 MOD 998244353
inline int read() {
	char ch = getchar(); int x = 0, f = 1;
	while(ch < '0' || ch > '9') {
		if(ch == '-') f = -1;
		ch = getchar();
	}
	while('0' <= ch && ch <= '9') {
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return x * f;
}
char s[200010];
int f[200010][3][3][2];
set<string> S;
inline void dfs(string st) {
	//cerr << "string " << st << endl;
	int n = st.size();
	for(int i = 0; i + 1 < n; ++ i) {
		if(st[i] == st[i + 1]) continue;
		string en = st;
		char New = 3 - (st[i] - 'a') - (st[i + 1] - 'a') + 'a';
		en[i] = en[i + 1] = New;
		if(S.find(en) == S.end()) {
			S.insert(en);
			dfs(en);
		}
	}
}
inline void solve(int n){
	string st = "";
	for(int i = 1; i <= n; ++ i) {
		st += s[i];
	}
	S.insert(st);
	//cerr << st << endl;
	dfs(st);
	printf("%d\n", S.size());
}
int main() {
	//freopen("a.in", "r", stdin);
	scanf("%s", s + 1);
	int n = strlen(s + 1);
	if(n <= 3) solve(n);
	else {
		int flag = 0;
		for(int i = 1; i < n; ++ i) {
			if(s[i] != s[i + 1]) ++ flag;
		}
		int Sum = 0;
		for(int i = 1; i <= n; ++ i) {
			Sum += s[i] - 'a';
		}
		Sum %= 3;
		if(!flag) {
			return puts("1"), 0;
		}
		f[1][0][0][0] = f[1][1][1][0] = f[1][2][2][0] = 1;
		for(int i = 1; i < n; ++ i) {
			for(int j = 0; j <= 2; ++ j) {
				for(int k = 0; k <= 2; ++ k) {
					for(int w = 0; w <= 1; ++ w) {
						for(int t = 0; t <= 2; ++ t) {
							(f[i + 1][t][(k + t) % 3][w | (t == j)] += f[i][j][k][w]) %= MOD;
						}
					}
				}
			}
		}
		int Ans = 0;
		for(int i = 0; i <= 2; ++ i) {
			Ans += f[n][i][Sum][1];
			Ans %= MOD;
		} 
		if(flag == n - 1) (++ Ans) %= MOD;
		printf("%d\n", Ans);
	}
} 
```