#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
const int maxN = 2 * 1e5 + 5;
ll dp[maxN][3][2][4];
char s[maxN];
int val, N;
bool same() {
	N = strlen(s + 1);
	for(int i = 1; i <= N; ++i) val = (val + s[i] - 'a') % 3;
	for(int i = 2; i <= N; ++i)
	if(s[i] != s[1]) return 0;
	return 1;
}
int main() {
	scanf("%s", s + 1);
	if(same()) {
		printf("1\n"); return 0;
	}
	if(N==2)puts("2"),exit(0);
	if(N==3) {
		if(s[1]!=s[2]&&s[1]!=s[3]&&s[2]!=s[3])puts("3"),exit(0);
		if(s[1]==s[2]||s[2]==s[3])puts("6");
		if(s[1]==s[3])puts("7");
		exit(0);
	}
	dp[0][0][0][3] = 1;
	for(int i = 0; i < N; ++i) {
		for(int mo = 0; mo < 3; ++mo)
		for(int j = 0; j < 2; ++j) {
			for(int k = 0; k <= 3; ++k) {
				if(dp[i][mo][j][k] == 0) continue;
				for(int k_ = 0; k_ < 3; ++k_) {
					ll& t = dp[i + 1][(mo + k_) % 3][j | (k_ == k)][k_];
					t += dp[i][mo][j][k];
					t %= mod;
				}
			}
		}
	}
	ll ans = 0;
	for(int i = 0; i < 3; ++i)
	ans = (ans + dp[N][val][1][i]) % mod;
	ans++;
	for(int i = 1; i <= N - 1; ++i) {
		if(s[i] == s[i + 1]) {
			ans--; break;
		}
	}
	ans = (ans + mod) % mod;
	printf("%lld\n", ans);
	return 0;
} 
### Prompt

Please create a solution in cpp 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 <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
const int maxN = 2 * 1e5 + 5;
ll dp[maxN][3][2][4];
char s[maxN];
int val, N;
bool same() {
	N = strlen(s + 1);
	for(int i = 1; i <= N; ++i) val = (val + s[i] - 'a') % 3;
	for(int i = 2; i <= N; ++i)
	if(s[i] != s[1]) return 0;
	return 1;
}
int main() {
	scanf("%s", s + 1);
	if(same()) {
		printf("1\n"); return 0;
	}
	if(N==2)puts("2"),exit(0);
	if(N==3) {
		if(s[1]!=s[2]&&s[1]!=s[3]&&s[2]!=s[3])puts("3"),exit(0);
		if(s[1]==s[2]||s[2]==s[3])puts("6");
		if(s[1]==s[3])puts("7");
		exit(0);
	}
	dp[0][0][0][3] = 1;
	for(int i = 0; i < N; ++i) {
		for(int mo = 0; mo < 3; ++mo)
		for(int j = 0; j < 2; ++j) {
			for(int k = 0; k <= 3; ++k) {
				if(dp[i][mo][j][k] == 0) continue;
				for(int k_ = 0; k_ < 3; ++k_) {
					ll& t = dp[i + 1][(mo + k_) % 3][j | (k_ == k)][k_];
					t += dp[i][mo][j][k];
					t %= mod;
				}
			}
		}
	}
	ll ans = 0;
	for(int i = 0; i < 3; ++i)
	ans = (ans + dp[N][val][1][i]) % mod;
	ans++;
	for(int i = 1; i <= N - 1; ++i) {
		if(s[i] == s[i + 1]) {
			ans--; break;
		}
	}
	ans = (ans + mod) % mod;
	printf("%lld\n", ans);
	return 0;
} 
```