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

#define rep(i,l,r) for(register int i = l ; i <= r ; i++)
#define repd(i,r,l) for(register int i = r ; i >= l ; i--)
#define rvc(i,S) for(register int i = 0 ; i < (int)S.size() ; i++)
#define rvcd(i,S) for(register int i = ((int)S.size()) - 1 ; i >= 0 ; i--)
#define fore(i,x)for (register int i = head[x] ; i ; i = e[i].next)
#define forup(i,l,r) for (register int i = l ; i <= r ; i += lowbit(i))
#define fordown(i,id) for (register int i = id ; i ; i -= lowbit(i))
#define pb push_back
#define prev prev_
#define stack stack_
#define mp make_pair
#define fi first
#define se second
#define lowbit(x) ((x)&(-(x)))

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pr;

const ld inf = 2e18;
const int N = 3e6 + 10;
const int maxn = 200020;
const ll mod = 998244353;

ll f[maxn][3][2][3],ans;
char ch[maxn];
int n,t;

inline ll power(ll x,ll y){
	y = ((y % (mod - 1)) + (mod - 1)) % (mod - 1);
//	if ( y < 0 ) return power(power(x,-y),mod - 2);
	ll res = 1;
	while ( y ){
		if ( y & 1 ) res = res * x % mod;
		x = x * x % mod;
		y >>= 1;
	}
	return res;
}
bool allsame(){
	rep(i,1,n - 1) if ( ch[i] != ch[i + 1] ) return 0;
	return 1;
}
bool alldiff(){
	rep(i,1,n - 1) if ( ch[i] == ch[i + 1] ) return 0;
	return 1;
}
inline void up(ll &x,ll y){ x = (x + y) % mod; }
int main(){
	scanf("%s",ch + 1);
	n = strlen(ch + 1);
	if ( allsame() ) return puts("1"),0;
	if ( n == 2 ){
		puts("2");
		return 0;
	}
	if ( n == 3 ){
		if ( alldiff() ){
		   	if ( ch[1] != ch[3] ) puts("3");
			else puts("7");
		}
		else puts("6");
		return 0;
	}
	rep(i,1,n) t += ch[i] - 'a';
	//f[0][0][0] = 1;
	rep(k,0,2) f[1][k][0][k] = 1;
	rep(i,2,n){
		rep(t,0,2){
			rep(x,0,2){
				rep(y,0,2){	
					if ( x != y ) up(f[i][(t + x) % 3][0][x],f[i - 1][t][0][y]);
					else up(f[i][(t + x) % 3][1][y],f[i - 1][t][0][y]);
					up(f[i][(t + x) % 3][1][x],f[i - 1][t][1][y]);
		//			if ( i > 1 ) up(f[i][(t + 2 * x) % 3][1],f[i - 2][t][0]);
				}
			}
		}
	}
	t %= 3;
	rep(k,0,2){
		up(ans,f[n][t][1][k]);
	}
	//ans = power(3,n - 1) - power(2,n - 1) + mod;
	if ( alldiff() ) ans++;
	cout<<ans % mod<<endl;
}

### 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<bits/stdc++.h>
using namespace std;

#define rep(i,l,r) for(register int i = l ; i <= r ; i++)
#define repd(i,r,l) for(register int i = r ; i >= l ; i--)
#define rvc(i,S) for(register int i = 0 ; i < (int)S.size() ; i++)
#define rvcd(i,S) for(register int i = ((int)S.size()) - 1 ; i >= 0 ; i--)
#define fore(i,x)for (register int i = head[x] ; i ; i = e[i].next)
#define forup(i,l,r) for (register int i = l ; i <= r ; i += lowbit(i))
#define fordown(i,id) for (register int i = id ; i ; i -= lowbit(i))
#define pb push_back
#define prev prev_
#define stack stack_
#define mp make_pair
#define fi first
#define se second
#define lowbit(x) ((x)&(-(x)))

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pr;

const ld inf = 2e18;
const int N = 3e6 + 10;
const int maxn = 200020;
const ll mod = 998244353;

ll f[maxn][3][2][3],ans;
char ch[maxn];
int n,t;

inline ll power(ll x,ll y){
	y = ((y % (mod - 1)) + (mod - 1)) % (mod - 1);
//	if ( y < 0 ) return power(power(x,-y),mod - 2);
	ll res = 1;
	while ( y ){
		if ( y & 1 ) res = res * x % mod;
		x = x * x % mod;
		y >>= 1;
	}
	return res;
}
bool allsame(){
	rep(i,1,n - 1) if ( ch[i] != ch[i + 1] ) return 0;
	return 1;
}
bool alldiff(){
	rep(i,1,n - 1) if ( ch[i] == ch[i + 1] ) return 0;
	return 1;
}
inline void up(ll &x,ll y){ x = (x + y) % mod; }
int main(){
	scanf("%s",ch + 1);
	n = strlen(ch + 1);
	if ( allsame() ) return puts("1"),0;
	if ( n == 2 ){
		puts("2");
		return 0;
	}
	if ( n == 3 ){
		if ( alldiff() ){
		   	if ( ch[1] != ch[3] ) puts("3");
			else puts("7");
		}
		else puts("6");
		return 0;
	}
	rep(i,1,n) t += ch[i] - 'a';
	//f[0][0][0] = 1;
	rep(k,0,2) f[1][k][0][k] = 1;
	rep(i,2,n){
		rep(t,0,2){
			rep(x,0,2){
				rep(y,0,2){	
					if ( x != y ) up(f[i][(t + x) % 3][0][x],f[i - 1][t][0][y]);
					else up(f[i][(t + x) % 3][1][y],f[i - 1][t][0][y]);
					up(f[i][(t + x) % 3][1][x],f[i - 1][t][1][y]);
		//			if ( i > 1 ) up(f[i][(t + 2 * x) % 3][1],f[i - 2][t][0]);
				}
			}
		}
	}
	t %= 3;
	rep(k,0,2){
		up(ans,f[n][t][1][k]);
	}
	//ans = power(3,n - 1) - power(2,n - 1) + mod;
	if ( alldiff() ) ans++;
	cout<<ans % mod<<endl;
}

```