#include <bits/stdc++.h>

using namespace std;

#define DBG cerr << '!' << endl;
#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(ll (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(ll (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int W = 0;W < (n);W++)cerr << v[W] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(10)
#define INF 1000000000
#define MOD 998244353

typedef long long ll;
typedef pair<ll,ll> P;
set<string> s;
ll ans;
ll dp[222222][3][4][4];

void zentan(string str){
	ans++;
	//cout << str << endl;
	s.insert(str);
	REP(i,str.size()-1){
		if(str[i] != str[i+1]){
			string tmp = str;
			REP(j,3){
				if(str[i] != (char)('a'+j) && str[i+1] != (char)('a'+j)){
					tmp[i] = (char)('a'+j);
					tmp[i+1] = (char)('a'+j);
					if(s.find(tmp) == s.end()){
						zentan(tmp);
					}
				}
			}
		}
	}
}
			

int main()
{
	string str;cin >> str;
	if(str.size() < 5){
		zentan(str);
		cout << ans << endl;
		return 0;
	}
	dp[1][0][0][0] = 1;
	dp[1][0][1][1] = 1;
	dp[1][0][2][2] = 1;
	ll difff = 0;
	ll md = 0;
	REP(i,str.size()){
		REP(j,3){
			REP(k,3){
				REP(l,3){
					if(j == k)dp[i+1][1][k][(k+l)%3] = (dp[i+1][1][k][(k+l)%3] + dp[i][0][j][l]) % MOD;
					else dp[i+1][0][k][(k+l)%3] = (dp[i+1][0][k][(k+l)%3] + dp[i][0][j][l]) % MOD;
					dp[i+1][1][k][(k+l)%3] = (dp[i+1][1][k][(k+l)%3] + dp[i][1][j][l]) % MOD;
				}
			}	
		}
		if(i != str.size() - 1 && str[i] != str[i+1])difff++;
		md = (md + (str[i] - 'a')) % 3;
	}
	REP(i,3)ans = (dp[str.size()][1][i][md] + ans) % MOD;
	if(difff == str.size()-1)ans = (ans + 1) % MOD;
	if(difff == 0)ans = 1;
			
	cout << ans << endl;
	return 0;
}
### Prompt

Please formulate 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>

using namespace std;

#define DBG cerr << '!' << endl;
#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(ll (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(ll (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int W = 0;W < (n);W++)cerr << v[W] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(10)
#define INF 1000000000
#define MOD 998244353

typedef long long ll;
typedef pair<ll,ll> P;
set<string> s;
ll ans;
ll dp[222222][3][4][4];

void zentan(string str){
	ans++;
	//cout << str << endl;
	s.insert(str);
	REP(i,str.size()-1){
		if(str[i] != str[i+1]){
			string tmp = str;
			REP(j,3){
				if(str[i] != (char)('a'+j) && str[i+1] != (char)('a'+j)){
					tmp[i] = (char)('a'+j);
					tmp[i+1] = (char)('a'+j);
					if(s.find(tmp) == s.end()){
						zentan(tmp);
					}
				}
			}
		}
	}
}
			

int main()
{
	string str;cin >> str;
	if(str.size() < 5){
		zentan(str);
		cout << ans << endl;
		return 0;
	}
	dp[1][0][0][0] = 1;
	dp[1][0][1][1] = 1;
	dp[1][0][2][2] = 1;
	ll difff = 0;
	ll md = 0;
	REP(i,str.size()){
		REP(j,3){
			REP(k,3){
				REP(l,3){
					if(j == k)dp[i+1][1][k][(k+l)%3] = (dp[i+1][1][k][(k+l)%3] + dp[i][0][j][l]) % MOD;
					else dp[i+1][0][k][(k+l)%3] = (dp[i+1][0][k][(k+l)%3] + dp[i][0][j][l]) % MOD;
					dp[i+1][1][k][(k+l)%3] = (dp[i+1][1][k][(k+l)%3] + dp[i][1][j][l]) % MOD;
				}
			}	
		}
		if(i != str.size() - 1 && str[i] != str[i+1])difff++;
		md = (md + (str[i] - 'a')) % 3;
	}
	REP(i,3)ans = (dp[str.size()][1][i][md] + ans) % MOD;
	if(difff == str.size()-1)ans = (ans + 1) % MOD;
	if(difff == 0)ans = 1;
			
	cout << ans << endl;
	return 0;
}
```