#include<stdio.h>
#include<vector>
#include<algorithm>
#include<string>
#include<iostream>
#include<set>
using namespace std;
typedef long long ll;
ll mod = 998244353;
ll dp[303030][3][3][2];
set<string>se;
void dfs(string s)
{
	if (se.find(s) != se.end())return;
	se.insert(s);
	for (int i = 0; i < s.size() - 1; i++)
	{
		if (s[i] != s[i + 1])
		{
			string z = s;
			z[i] = z[i + 1] = int('a') + int('b') + int('c') - s[i] - s[i + 1];
			dfs(z);
		}
	}
}
int main()
{
	string s;
	cin >> s;
	se.clear();
	for (int i = 0; i <= s.size(); i++)for (int j = 0; j < 3; j++)for (int k = 0; k < 3; k++)for (int l = 0; l < 2; l++)dp[i][j][k][l] = 0;
	if (s.size() <= 3)
	{
		dfs(s);
		printf("%d\n", se.size());
	}
	else
	{
		bool f1 = false, f2 = false;
		int cnt = 0;
		for (int i = 0; i < s.size(); i++)cnt += s[i] - 'a';
		for (int i = 0; i < s.size() - 1; i++)
		{
			if (s[i] != s[i + 1])f1 = true;
			else f2 = true;
		}
		cnt %= 3;
		if (!f1)printf("1\n");
		else
		{
			dp[1][0][0][0] = dp[1][1][1][0] = dp[1][2][2][0] = 1;
			for (int i = 1; i < s.size(); 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)
							{
								dp[i + 1][(j + l) % 3][l][1] += dp[i][j][k][0] + dp[i][j][k][1];
							}
							else
							{
								dp[i + 1][(j + l) % 3][l][0] += dp[i][j][k][0];
								dp[i + 1][(j + l) % 3][l][1] += dp[i][j][k][1];
							}
						}
					}
				}
				for (int j = 0; j < 3; j++)for (int k = 0; k < 3; k++)for (int l = 0; l < 2; l++)dp[i + 1][j][k][l] %= mod;
			}
			ll ans = 0;
			for (int i = 0; i < 3; i++)ans += dp[s.size()][cnt][i][1];
			if (!f2)ans++;
			printf("%lld\n", ans%mod);
		}
	}
}

### Prompt

Create a solution in CPP for 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<stdio.h>
#include<vector>
#include<algorithm>
#include<string>
#include<iostream>
#include<set>
using namespace std;
typedef long long ll;
ll mod = 998244353;
ll dp[303030][3][3][2];
set<string>se;
void dfs(string s)
{
	if (se.find(s) != se.end())return;
	se.insert(s);
	for (int i = 0; i < s.size() - 1; i++)
	{
		if (s[i] != s[i + 1])
		{
			string z = s;
			z[i] = z[i + 1] = int('a') + int('b') + int('c') - s[i] - s[i + 1];
			dfs(z);
		}
	}
}
int main()
{
	string s;
	cin >> s;
	se.clear();
	for (int i = 0; i <= s.size(); i++)for (int j = 0; j < 3; j++)for (int k = 0; k < 3; k++)for (int l = 0; l < 2; l++)dp[i][j][k][l] = 0;
	if (s.size() <= 3)
	{
		dfs(s);
		printf("%d\n", se.size());
	}
	else
	{
		bool f1 = false, f2 = false;
		int cnt = 0;
		for (int i = 0; i < s.size(); i++)cnt += s[i] - 'a';
		for (int i = 0; i < s.size() - 1; i++)
		{
			if (s[i] != s[i + 1])f1 = true;
			else f2 = true;
		}
		cnt %= 3;
		if (!f1)printf("1\n");
		else
		{
			dp[1][0][0][0] = dp[1][1][1][0] = dp[1][2][2][0] = 1;
			for (int i = 1; i < s.size(); 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)
							{
								dp[i + 1][(j + l) % 3][l][1] += dp[i][j][k][0] + dp[i][j][k][1];
							}
							else
							{
								dp[i + 1][(j + l) % 3][l][0] += dp[i][j][k][0];
								dp[i + 1][(j + l) % 3][l][1] += dp[i][j][k][1];
							}
						}
					}
				}
				for (int j = 0; j < 3; j++)for (int k = 0; k < 3; k++)for (int l = 0; l < 2; l++)dp[i + 1][j][k][l] %= mod;
			}
			ll ans = 0;
			for (int i = 0; i < 3; i++)ans += dp[s.size()][cnt][i][1];
			if (!f2)ans++;
			printf("%lld\n", ans%mod);
		}
	}
}

```