/*
If all letters in S are the same, print 1.
If |S| <= 3, burte force. 
Otherwise, count the number of strings T such that
--- |T| = |S|
--- sum(S) = sum(T) mod 3
--- There is at least one pair of adjacent same letters in T
*/
#include <bits/stdc++.h>

using namespace std;

const int MOD = 998244353;
const int MAXN = 200005;

string s;

int f[MAXN][3][3][2];

int n;

set<string> myset;
set<char> char_set;

void dfs(string x)
{
	for (int i = 0; i + 1 < n; i++)
	{
		if (x[i] != x[i + 1])
		{
			string y = x;
			for (char c = 'a'; c <= 'c'; c++)
				if (x[i] != c && x[i + 1] != c)
					y[i] = y[i + 1] = c;
			if (!myset.count(y))
			{
				myset.insert(y);
				dfs(y);
			}
		}
	}
}

void brute()
{
	myset.insert(s);
	dfs(s);
	cout << myset.size() << endl;
	exit(0);
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);
	cin >> s, n = s.size();
	if (n <= 3)
		brute();
	else
	{
		f[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++)
					{
						if (!f[i][j][k][l])
							continue;
						int cur = f[i][j][k][l];	
						for (int w = 0; w < 3; w++)
							(f[i + 1][w][(k + w) % 3][((i > 0 && (w == j)) ? 1 : 0) | l] += cur) %= MOD;
					}
				}
			}
		}
		int x = 0;
		for (auto c : s)
			(x += c - 'a') %= 3, char_set.insert(c);
		if (char_set.size() == 1)
		{
			cout << 1 << endl;
			exit(0);	
		}
		int res = 0;
		for (int j = 0; j < 3; j++)
			(res += f[n][j][x][1]) %= MOD;
		bool ch = 1;
		for (int i = 0; i + 1 < n; i++)
			ch &= (s[i] != s[i + 1]);
		if (ch)
			(res += 1) %= MOD;
		cout << res << endl;
	}
	return 0;	
}

### Prompt

Please provide a Cpp coded solution to the problem described below:

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
/*
If all letters in S are the same, print 1.
If |S| <= 3, burte force. 
Otherwise, count the number of strings T such that
--- |T| = |S|
--- sum(S) = sum(T) mod 3
--- There is at least one pair of adjacent same letters in T
*/
#include <bits/stdc++.h>

using namespace std;

const int MOD = 998244353;
const int MAXN = 200005;

string s;

int f[MAXN][3][3][2];

int n;

set<string> myset;
set<char> char_set;

void dfs(string x)
{
	for (int i = 0; i + 1 < n; i++)
	{
		if (x[i] != x[i + 1])
		{
			string y = x;
			for (char c = 'a'; c <= 'c'; c++)
				if (x[i] != c && x[i + 1] != c)
					y[i] = y[i + 1] = c;
			if (!myset.count(y))
			{
				myset.insert(y);
				dfs(y);
			}
		}
	}
}

void brute()
{
	myset.insert(s);
	dfs(s);
	cout << myset.size() << endl;
	exit(0);
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);
	cin >> s, n = s.size();
	if (n <= 3)
		brute();
	else
	{
		f[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++)
					{
						if (!f[i][j][k][l])
							continue;
						int cur = f[i][j][k][l];	
						for (int w = 0; w < 3; w++)
							(f[i + 1][w][(k + w) % 3][((i > 0 && (w == j)) ? 1 : 0) | l] += cur) %= MOD;
					}
				}
			}
		}
		int x = 0;
		for (auto c : s)
			(x += c - 'a') %= 3, char_set.insert(c);
		if (char_set.size() == 1)
		{
			cout << 1 << endl;
			exit(0);	
		}
		int res = 0;
		for (int j = 0; j < 3; j++)
			(res += f[n][j][x][1]) %= MOD;
		bool ch = 1;
		for (int i = 0; i + 1 < n; i++)
			ch &= (s[i] != s[i + 1]);
		if (ch)
			(res += 1) %= MOD;
		cout << res << endl;
	}
	return 0;	
}

```