#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <set>
#include <map>
#define MOD 998244353
#define my_abs(x) ((x) < 0 ? -(x) : (x))
#define mp std::make_pair
#define pb push_back
#define X first
#define Y second
typedef long long ll; 
char str[200005]; 
int dp[200005][3][3][2]; 
int main()
{
	// freopen("ARC094-F.in", "r", stdin);
	scanf("%s", str); 
	int n = strlen(str), cnt = 0, sum = 0; 
	for (int i = 0; i < n; i++)
	{
		cnt += i && str[i - 1] != str[i]; 
		(sum += str[i] - 'a') %= 3; 
	}
	if (!cnt)
	{
		puts("1"); 
		return 0; 
	}
	if (n <= 3)
	{
		if (n == 2)
			puts("2"); 
		else
		{
			if (cnt != n - 1)
				puts("6"); 
			else if (str[0] == str[2])
				puts("7"); 
			else
				puts("3"); 
		}
		return 0; 
	}
	dp[1][0][0][0] = dp[1][1][1][0] = dp[1][2][2][0] = 1; 
	for (int i = 1; i < n; i++)
	{
		for (int x = 0; x < 3; x++)
		{
			for (int y = 0; y < 3; y++)
			{
				for (int f = 0; f < 2; f++)
				{
					for (int z = 0; z < 3; z++)
						(dp[i + 1][z][(y + z) % 3][f | (x == z)] += dp[i][x][y][f]) %= MOD; 
				}
			}
		}
	}
	int ans = cnt == n - 1; 
	for (int i = 0; i < 3; i++)
		(ans += dp[n][i][sum][1]) %= MOD; 
	printf("%d\n", ans);
	return 0; 
}

### 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 <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <set>
#include <map>
#define MOD 998244353
#define my_abs(x) ((x) < 0 ? -(x) : (x))
#define mp std::make_pair
#define pb push_back
#define X first
#define Y second
typedef long long ll; 
char str[200005]; 
int dp[200005][3][3][2]; 
int main()
{
	// freopen("ARC094-F.in", "r", stdin);
	scanf("%s", str); 
	int n = strlen(str), cnt = 0, sum = 0; 
	for (int i = 0; i < n; i++)
	{
		cnt += i && str[i - 1] != str[i]; 
		(sum += str[i] - 'a') %= 3; 
	}
	if (!cnt)
	{
		puts("1"); 
		return 0; 
	}
	if (n <= 3)
	{
		if (n == 2)
			puts("2"); 
		else
		{
			if (cnt != n - 1)
				puts("6"); 
			else if (str[0] == str[2])
				puts("7"); 
			else
				puts("3"); 
		}
		return 0; 
	}
	dp[1][0][0][0] = dp[1][1][1][0] = dp[1][2][2][0] = 1; 
	for (int i = 1; i < n; i++)
	{
		for (int x = 0; x < 3; x++)
		{
			for (int y = 0; y < 3; y++)
			{
				for (int f = 0; f < 2; f++)
				{
					for (int z = 0; z < 3; z++)
						(dp[i + 1][z][(y + z) % 3][f | (x == z)] += dp[i][x][y][f]) %= MOD; 
				}
			}
		}
	}
	int ans = cnt == n - 1; 
	for (int i = 0; i < 3; i++)
		(ans += dp[n][i][sum][1]) %= MOD; 
	printf("%d\n", ans);
	return 0; 
}

```