#include<bits/stdc++.h>
#define For(i,l,r) for(int i = (l),i##end = (r);i <= i##end;i++)
#define Fordown(i,r,l) for(int i = (r),i##end = (l);i >= i##end;i--)
#define debug(x) cout << #x << " = " << x << endl

using namespace std;

typedef long long ll;

template <typename T> inline bool chkmin(T &x,T y) { return y < x ? x = y,1 : 0; }
template <typename T> inline bool chkmax(T &x,T y) { return x < y ? x = y,1 : 0; }

const int INF = 0x3f3f3f3f;
const int N = 2e5 + 10,mod = 998244353;

int dp[N][3][3];
char str[N];

inline int read() {
	int x = 0,flag = 1;
	char ch = getchar();
	while(!isdigit(ch) && ch != '-')ch = getchar();
	if(ch == '-')flag = -1,ch = getchar();
	while(isdigit(ch))x = (x << 3) + (x << 1) + (ch - '0'),ch = getchar();
	return x * flag;
}

inline void Add(int &x,int y) {
	if((x += y) >= mod) x -= mod;
}

int main() {
	scanf("%s",str + 1);
	int n = strlen(str + 1);
	if(n == 2) return printf("%d\n",2 - (str[1] == str[2])),0;
	if(n == 3) {
		if(str[1] == str[2] && str[2] == str[3]) return puts("1"),0;
		else if(str[1] == str[2] || str[2] == str[3]) return puts("6"),0;
		else if(str[1] == str[3]) return puts("7"),0;
		else return puts("3"),0;
	}

	int ans = 1;
	For(i,1,n - 1) ans = 1ll * ans * 3 % mod;

	For(i,0,2) dp[1][i][i] = 1;
	For(i,2,n) For(j,0,2) For(k,0,2) if(dp[i - 1][j][k])
		For(l,0,2) if(l != j) Add(dp[i][l][(k + l) % 3],dp[i - 1][j][k]);

	int Sum = 0;bool flag1 = true,flag2 = true;
	For(i,1,n) {
		Sum += str[i] - 'a';
		if(i == n) break;
		if(str[i] == str[i + 1]) flag1 = false;
		if(str[i] != str[i + 1]) flag2 = false;
	}
	Sum %= 3,ans += flag1;
	For(i,0,2) ans = (ans - dp[n][i][Sum] + mod) % mod;

	if(flag2) puts("1");
	else printf("%d\n",ans);

	return 0;
}
### Prompt

Your challenge is to write 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>
#define For(i,l,r) for(int i = (l),i##end = (r);i <= i##end;i++)
#define Fordown(i,r,l) for(int i = (r),i##end = (l);i >= i##end;i--)
#define debug(x) cout << #x << " = " << x << endl

using namespace std;

typedef long long ll;

template <typename T> inline bool chkmin(T &x,T y) { return y < x ? x = y,1 : 0; }
template <typename T> inline bool chkmax(T &x,T y) { return x < y ? x = y,1 : 0; }

const int INF = 0x3f3f3f3f;
const int N = 2e5 + 10,mod = 998244353;

int dp[N][3][3];
char str[N];

inline int read() {
	int x = 0,flag = 1;
	char ch = getchar();
	while(!isdigit(ch) && ch != '-')ch = getchar();
	if(ch == '-')flag = -1,ch = getchar();
	while(isdigit(ch))x = (x << 3) + (x << 1) + (ch - '0'),ch = getchar();
	return x * flag;
}

inline void Add(int &x,int y) {
	if((x += y) >= mod) x -= mod;
}

int main() {
	scanf("%s",str + 1);
	int n = strlen(str + 1);
	if(n == 2) return printf("%d\n",2 - (str[1] == str[2])),0;
	if(n == 3) {
		if(str[1] == str[2] && str[2] == str[3]) return puts("1"),0;
		else if(str[1] == str[2] || str[2] == str[3]) return puts("6"),0;
		else if(str[1] == str[3]) return puts("7"),0;
		else return puts("3"),0;
	}

	int ans = 1;
	For(i,1,n - 1) ans = 1ll * ans * 3 % mod;

	For(i,0,2) dp[1][i][i] = 1;
	For(i,2,n) For(j,0,2) For(k,0,2) if(dp[i - 1][j][k])
		For(l,0,2) if(l != j) Add(dp[i][l][(k + l) % 3],dp[i - 1][j][k]);

	int Sum = 0;bool flag1 = true,flag2 = true;
	For(i,1,n) {
		Sum += str[i] - 'a';
		if(i == n) break;
		if(str[i] == str[i + 1]) flag1 = false;
		if(str[i] != str[i + 1]) flag2 = false;
	}
	Sum %= 3,ans += flag1;
	For(i,0,2) ans = (ans - dp[n][i][Sum] + mod) % mod;

	if(flag2) puts("1");
	else printf("%d\n",ans);

	return 0;
}
```