#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define LL long long
using namespace std;
const int Maxn = 2000010;
const int Mod = 998244353;
int mp[1000];
int f[Maxn][3][3];
char s[Maxn];
int a[Maxn];
int n;
void solve1() {
	queue <int> q;
	int x = 0;
	for(int i = 1; i <= n; i++) x = x * 10 + a[i];
	int ans = 0;
	mp[x] = 1; ans++;
	q.push(x);
	while(!q.empty()){
		x = q.front(); q.pop();
		int po = 1;
		for(int i = 1; i < n; i++){
			int a1 = (x/po)%10, a2 = (x/po/10)%10;
			if(a1 != a2){
				int a3 = 3-a1-a2;
				int y = x-a1*po-a2*po*10+a3*po*11;
				if(!mp[y]){ mp[y] = 1; ans++; q.push(y); }
			}
			po *= 10;
		}
	}
	printf("%d\n", ans);
}
void up(int &x, int y) { x = (x + y) % Mod; }
bool pd1() {
	for(int i = 1; i < n; i++) if(a[i] != a[i+1]) return false;
	return true;
}
bool pd2() {
	for(int i = 1; i < n; i++) if(a[i] == a[i+1]) return false;
	return true;
}
void solve2() {
	if(pd1() == true){ printf("1\n"); return; }
	int ans = 1;
	int i, j, k;
	for(i = 1; i < n; i++) ans = (LL)ans*3%Mod;
	for(i = 0; i < 3; i++) f[1][i][i] = 1;
	for(i = 1; i < n; i++){
		for(j = 0; j < 3; j++){
			for(k = 0; k < 3; k++){
				for(int x = 0; x < 3; x++) if(x != j) up(f[i+1][x][(k+x)%3], f[i][j][k]);
			}
		}
	}
	int sum = 0;
	for(i = 1; i <= n; i++) sum = (sum+a[i])%3;
	for(i = 0; i < 3; i++) ans = (ans-f[n][i][sum]+Mod)%Mod;
	if(pd2() == true) ans++;
	printf("%d\n", ans%Mod);
}
int main() {
	int i, j, k;
	scanf("%s", s+1);
	n = strlen(s+1);
	for(i = 1; i <= n; i++) a[i] = s[i]-'a';
	if(n <= 3) solve1();
	else solve2();
	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 <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define LL long long
using namespace std;
const int Maxn = 2000010;
const int Mod = 998244353;
int mp[1000];
int f[Maxn][3][3];
char s[Maxn];
int a[Maxn];
int n;
void solve1() {
	queue <int> q;
	int x = 0;
	for(int i = 1; i <= n; i++) x = x * 10 + a[i];
	int ans = 0;
	mp[x] = 1; ans++;
	q.push(x);
	while(!q.empty()){
		x = q.front(); q.pop();
		int po = 1;
		for(int i = 1; i < n; i++){
			int a1 = (x/po)%10, a2 = (x/po/10)%10;
			if(a1 != a2){
				int a3 = 3-a1-a2;
				int y = x-a1*po-a2*po*10+a3*po*11;
				if(!mp[y]){ mp[y] = 1; ans++; q.push(y); }
			}
			po *= 10;
		}
	}
	printf("%d\n", ans);
}
void up(int &x, int y) { x = (x + y) % Mod; }
bool pd1() {
	for(int i = 1; i < n; i++) if(a[i] != a[i+1]) return false;
	return true;
}
bool pd2() {
	for(int i = 1; i < n; i++) if(a[i] == a[i+1]) return false;
	return true;
}
void solve2() {
	if(pd1() == true){ printf("1\n"); return; }
	int ans = 1;
	int i, j, k;
	for(i = 1; i < n; i++) ans = (LL)ans*3%Mod;
	for(i = 0; i < 3; i++) f[1][i][i] = 1;
	for(i = 1; i < n; i++){
		for(j = 0; j < 3; j++){
			for(k = 0; k < 3; k++){
				for(int x = 0; x < 3; x++) if(x != j) up(f[i+1][x][(k+x)%3], f[i][j][k]);
			}
		}
	}
	int sum = 0;
	for(i = 1; i <= n; i++) sum = (sum+a[i])%3;
	for(i = 0; i < 3; i++) ans = (ans-f[n][i][sum]+Mod)%Mod;
	if(pd2() == true) ans++;
	printf("%d\n", ans%Mod);
}
int main() {
	int i, j, k;
	scanf("%s", s+1);
	n = strlen(s+1);
	for(i = 1; i <= n; i++) a[i] = s[i]-'a';
	if(n <= 3) solve1();
	else solve2();
	return 0;
}
```