#include <iostream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <cassert>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <string>
#include <algorithm>
#include <utility>
#define llint long long
#define inf 1e18
#define rep(x, s, t) for(llint (x) = (s); (x) < (t); (x)++)
#define Rep(x, s, t) for(llint (x) = (s); (x) <= (t); (x)++)
#define chmin(x, y) (x) = min((x), (y))
#define chmax(x, y) (x) = max((x), (y))
#define mod 998244353
using namespace std;
typedef pair<llint, llint> P;

string s;
llint dp[200005][3][3][2];
set<char> S;

int main(void)
{
	cin >> s;
	llint n = s.size(), p = 0;
	for(int i = 0; i < n; i++){
		p += s[i]-'a';
		S.insert(s[i]);
	}
	p %= 3;
	
	if(S.size() == 1){
		cout << 1 << endl;
		return 0;
	}
	if(n == 2){
		cout << 2 << endl;
		return 0;
	}
	if(n == 3 && S.size() == 3){
		cout << 3 << endl;
		return 0;
	}
	
	dp[0][0][0][0] = 1;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < 3; j++){
			for(int k = 0; k < 3; k++){
				for(int l = 0; l < 2; l++){
					for(int m = 0; m < 3; m++){
						llint nl = l;
						if(i > 0 && k == m) nl = 1;
						(dp[i+1][(j+m)%3][m][nl] += dp[i][j][k][l]) %= mod;
					}
				}
			}
		}
	}
	llint ans = 0;
	for(int k = 0; k < 3; k++) ans += dp[n][p][k][1], ans %= mod;
	
	bool flag = false;
	for(int i = 1; i < n; i++){
		if(s[i-1] == s[i]){
			flag = true;
			break;
		}
	}
	if(!flag) ans++, ans %= mod;
	
	cout << ans << endl;

	return 0;
}

### Prompt

Your task is to create 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 <iostream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <cassert>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <string>
#include <algorithm>
#include <utility>
#define llint long long
#define inf 1e18
#define rep(x, s, t) for(llint (x) = (s); (x) < (t); (x)++)
#define Rep(x, s, t) for(llint (x) = (s); (x) <= (t); (x)++)
#define chmin(x, y) (x) = min((x), (y))
#define chmax(x, y) (x) = max((x), (y))
#define mod 998244353
using namespace std;
typedef pair<llint, llint> P;

string s;
llint dp[200005][3][3][2];
set<char> S;

int main(void)
{
	cin >> s;
	llint n = s.size(), p = 0;
	for(int i = 0; i < n; i++){
		p += s[i]-'a';
		S.insert(s[i]);
	}
	p %= 3;
	
	if(S.size() == 1){
		cout << 1 << endl;
		return 0;
	}
	if(n == 2){
		cout << 2 << endl;
		return 0;
	}
	if(n == 3 && S.size() == 3){
		cout << 3 << endl;
		return 0;
	}
	
	dp[0][0][0][0] = 1;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < 3; j++){
			for(int k = 0; k < 3; k++){
				for(int l = 0; l < 2; l++){
					for(int m = 0; m < 3; m++){
						llint nl = l;
						if(i > 0 && k == m) nl = 1;
						(dp[i+1][(j+m)%3][m][nl] += dp[i][j][k][l]) %= mod;
					}
				}
			}
		}
	}
	llint ans = 0;
	for(int k = 0; k < 3; k++) ans += dp[n][p][k][1], ans %= mod;
	
	bool flag = false;
	for(int i = 1; i < n; i++){
		if(s[i-1] == s[i]){
			flag = true;
			break;
		}
	}
	if(!flag) ans++, ans %= mod;
	
	cout << ans << endl;

	return 0;
}

```