#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
using namespace std;
using pi = pair<int, int>;
using lint = long long;
const int MAXN = 200005;
const int mod = 998244353;

string str;
int dp[MAXN][3][4][2];

int f(int x, int y, int z, int ok){
	if(x == 0) return y == 0 && ok;
	if(~dp[x][y][z][ok]) return dp[x][y][z][ok];
	lint ret = 0;
	for(int i='a'; i<='c'; i++){
		bool nok = ok || (z + 'a' == i);
		ret += f(x - 1, (y + i - 'a') % 3, i - 'a', nok);
	}
	return dp[x][y][z][ok] = ret % mod;
}

set<string> s;

void dfs(string x){
	if(s.find(x) != s.end()) return;
	s.insert(x);
	for(int i=0; i+1<x.size(); i++){
		if(x[i] != x[i+1]){
			char t = 'a';
			while(t == x[i] || t == x[i+1]) t++;
			string n = x;;
			n[i] = n[i+1] = t;
			dfs(n);
		}
	}
}

int main(){
	cin >> str;
	if(count(str.begin(), str.end(), str[0]) == str.size()){
		cout << 1 << endl;
		return 0;
	}
	if(str.size() <= 3){
		dfs(str);
		cout << s.size() << endl;
		return 0;
	}
	int dap = 0;
	for(auto &i : str) dap += i - 'a';
	int tmp = 1;
	for(int i=1; i<str.size(); i++) if(str[i] == str[i-1]) tmp = 0;
	memset(dp, -1, sizeof(dp));
	cout << (tmp + f(str.size(), (3 * 696969 - dap) % 3, 3, 0)) % 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>
#define sz(v) ((int)(v).size())
using namespace std;
using pi = pair<int, int>;
using lint = long long;
const int MAXN = 200005;
const int mod = 998244353;

string str;
int dp[MAXN][3][4][2];

int f(int x, int y, int z, int ok){
	if(x == 0) return y == 0 && ok;
	if(~dp[x][y][z][ok]) return dp[x][y][z][ok];
	lint ret = 0;
	for(int i='a'; i<='c'; i++){
		bool nok = ok || (z + 'a' == i);
		ret += f(x - 1, (y + i - 'a') % 3, i - 'a', nok);
	}
	return dp[x][y][z][ok] = ret % mod;
}

set<string> s;

void dfs(string x){
	if(s.find(x) != s.end()) return;
	s.insert(x);
	for(int i=0; i+1<x.size(); i++){
		if(x[i] != x[i+1]){
			char t = 'a';
			while(t == x[i] || t == x[i+1]) t++;
			string n = x;;
			n[i] = n[i+1] = t;
			dfs(n);
		}
	}
}

int main(){
	cin >> str;
	if(count(str.begin(), str.end(), str[0]) == str.size()){
		cout << 1 << endl;
		return 0;
	}
	if(str.size() <= 3){
		dfs(str);
		cout << s.size() << endl;
		return 0;
	}
	int dap = 0;
	for(auto &i : str) dap += i - 'a';
	int tmp = 1;
	for(int i=1; i<str.size(); i++) if(str[i] == str[i-1]) tmp = 0;
	memset(dp, -1, sizeof(dp));
	cout << (tmp + f(str.size(), (3 * 696969 - dap) % 3, 3, 0)) % mod << endl;
}

```