#include <bits/stdc++.h>

using namespace std;
typedef long long nagai;

string cur;

int calc(string s)
{
	int ans = 0;
	for (auto& x : s)
		ans += x;
	return ans % 3;
}

int n;

vector<string> gg;

void gena(int x)
{
	if (cur.size() == n)
	{
		gg.push_back(cur);
		return;
	}
	for (char ch = 'a'; ch <= 'c'; ++ch)
	{
		cur.push_back(ch);
		gena(x + 1);
		cur.pop_back();
	}
}

bool bad(string s)
{
	for (int i = 0; i < n - 1; ++i)
		if (s[i + 1] == s[i])
			return true;
	return false;
}

void lol(string s)
{
	n = s.size();
	vector<string> q;
	set<string> used;
	used.insert(s);
	q.push_back(s);
	for (int i = 0; i < q.size(); ++i)
	{
		string x = q[i];
		for (int j = 0; j + 1 < x.size(); ++j)
			if (x[j] != x[j + 1])
			{
				char ch = 3 * 'b' - x[j] - x[j + 1];
				auto y = x;
				y[j] = y[j + 1] = ch;
				//cerr << x[j] + x[j + 1] - y[j] - y[j + 1] << '\n';
				if (!used.count(y))
					used.insert(y), q.push_back(y);
			}
		/*
			else
			{
				char ch = x[j] == 'a' ? 'b' : 'a';
				char ch1 = x[j] == 'b' ? 'c' : 'b';
				auto y = x;
				y[j] = ch;
				y[j + 1] = ch1;
				if (!used.count(y))
					used.insert(y), q.push_back(y);
				y[j] = ch1;
				y[j + 1] = ch;
				if (!used.count(y))
					used.insert(y), q.push_back(y);

			}
			*/
	}
	cout << q.size() << '\n';
}
int main()
{
	string s;
	cin >> s;
	bool fuck = true;
	for (int i = 0; i < s.size(); ++i)
		if (s[i] != s[0])
			fuck = false;
	if (fuck)
	{
		cout << 1 << endl;
		return 0;
	}
	if (s.size() <= 5)
	{
		lol(s);
		return 0;
	}
	n = s.size();
	nagai mod = 998244353;
	nagai cnt = 1;
	for (int i = 0; i < n - 1; ++i)
		cnt *= 3, cnt %= mod;
	vector<vector<vector<int>>> dp(n, vector<vector<int>>(3, vector<int>(3)));
	dp[0][0][0] = dp[0][1][1] = dp[0][2][2] = 1;
	for (int i = 0; i + 1 < n; ++i)
		for (int j = 0; j < 3; ++j)
			for (int k = 0; k < 3; ++k)
				for (int l = 0; l < 3; ++l)
				{
					if (k == l)
						continue;
					int j1 = j + l;
					if (j1 >= 3)
						j1 -= 3;
					dp[i + 1][j1][l] += dp[i][j][k];
					if (dp[i + 1][j1][l] >= mod)
						dp[i + 1][j1][l] -= mod;
				}
	int mem = calc(s);
	for (int i = 0; i < 3; ++i)
	{
		cnt -= dp[n - 1][mem][i];
	}
	if (!bad(s))
		++cnt;
	cnt %= mod;
	if (cnt < 0)
		cnt += mod;
	cout << cnt << '\n';
}

### Prompt

Develop a solution in cpp 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
#include <bits/stdc++.h>

using namespace std;
typedef long long nagai;

string cur;

int calc(string s)
{
	int ans = 0;
	for (auto& x : s)
		ans += x;
	return ans % 3;
}

int n;

vector<string> gg;

void gena(int x)
{
	if (cur.size() == n)
	{
		gg.push_back(cur);
		return;
	}
	for (char ch = 'a'; ch <= 'c'; ++ch)
	{
		cur.push_back(ch);
		gena(x + 1);
		cur.pop_back();
	}
}

bool bad(string s)
{
	for (int i = 0; i < n - 1; ++i)
		if (s[i + 1] == s[i])
			return true;
	return false;
}

void lol(string s)
{
	n = s.size();
	vector<string> q;
	set<string> used;
	used.insert(s);
	q.push_back(s);
	for (int i = 0; i < q.size(); ++i)
	{
		string x = q[i];
		for (int j = 0; j + 1 < x.size(); ++j)
			if (x[j] != x[j + 1])
			{
				char ch = 3 * 'b' - x[j] - x[j + 1];
				auto y = x;
				y[j] = y[j + 1] = ch;
				//cerr << x[j] + x[j + 1] - y[j] - y[j + 1] << '\n';
				if (!used.count(y))
					used.insert(y), q.push_back(y);
			}
		/*
			else
			{
				char ch = x[j] == 'a' ? 'b' : 'a';
				char ch1 = x[j] == 'b' ? 'c' : 'b';
				auto y = x;
				y[j] = ch;
				y[j + 1] = ch1;
				if (!used.count(y))
					used.insert(y), q.push_back(y);
				y[j] = ch1;
				y[j + 1] = ch;
				if (!used.count(y))
					used.insert(y), q.push_back(y);

			}
			*/
	}
	cout << q.size() << '\n';
}
int main()
{
	string s;
	cin >> s;
	bool fuck = true;
	for (int i = 0; i < s.size(); ++i)
		if (s[i] != s[0])
			fuck = false;
	if (fuck)
	{
		cout << 1 << endl;
		return 0;
	}
	if (s.size() <= 5)
	{
		lol(s);
		return 0;
	}
	n = s.size();
	nagai mod = 998244353;
	nagai cnt = 1;
	for (int i = 0; i < n - 1; ++i)
		cnt *= 3, cnt %= mod;
	vector<vector<vector<int>>> dp(n, vector<vector<int>>(3, vector<int>(3)));
	dp[0][0][0] = dp[0][1][1] = dp[0][2][2] = 1;
	for (int i = 0; i + 1 < n; ++i)
		for (int j = 0; j < 3; ++j)
			for (int k = 0; k < 3; ++k)
				for (int l = 0; l < 3; ++l)
				{
					if (k == l)
						continue;
					int j1 = j + l;
					if (j1 >= 3)
						j1 -= 3;
					dp[i + 1][j1][l] += dp[i][j][k];
					if (dp[i + 1][j1][l] >= mod)
						dp[i + 1][j1][l] -= mod;
				}
	int mem = calc(s);
	for (int i = 0; i < 3; ++i)
	{
		cnt -= dp[n - 1][mem][i];
	}
	if (!bad(s))
		++cnt;
	cnt %= mod;
	if (cnt < 0)
		cnt += mod;
	cout << cnt << '\n';
}

```