# include <iostream>
# include <cstdio>
# include <cstring>
using namespace std;
const int N = 2e5 + 12;
const int mod = 998244353;
char s[N];int len,g,f[N][3][3][2];
bool same(){for(int i = 2;i <= len;i++)if(s[i] != s[i - 1])return false;return true;}
bool notsame(){for(int i = 2;i <= len;i++)if(s[i] == s[i - 1])return false;return true;}
int main()
{
     scanf("%s",s + 1);len = strlen(s + 1);
     if(same())puts("1");
     else if(len <= 3)
     {
     	if(len == 2){puts("2");}
     	else 
     	{
     		if(s[1] != s[2] && s[1] != s[3] && s[2] != s[3])puts("3");
     		else if(s[1] == s[3])puts("7");
     		else puts("6");
     	}
     }
     else 
     {
     	for(int i = 1;i <= len;i++)g = (g + s[i] - 'a') % 3;
     	for(int i = 0;i < 3;i++)f[1][i][i][0] = 1;
     	for(int i = 1;i < len;i++)
     	 for(int j = 0;j < 3;j++)
     	  for(int k = 0;k < 3;k++)
     	   for(int l = 0;l < 2;l++)
     	    for(int t = 0;t < 3;t++)
     	    (f[i + 1][t][(k + t) % 3][l | (t == j)] += f[i][j][k][l]) %= mod;
     	int ret = ((f[len][0][g][1] + f[len][1][g][1]) % mod + f[len][2][g][1]) % mod;
     	printf("%d\n",(ret + notsame()) % mod);
     }
}
### 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 <iostream>
# include <cstdio>
# include <cstring>
using namespace std;
const int N = 2e5 + 12;
const int mod = 998244353;
char s[N];int len,g,f[N][3][3][2];
bool same(){for(int i = 2;i <= len;i++)if(s[i] != s[i - 1])return false;return true;}
bool notsame(){for(int i = 2;i <= len;i++)if(s[i] == s[i - 1])return false;return true;}
int main()
{
     scanf("%s",s + 1);len = strlen(s + 1);
     if(same())puts("1");
     else if(len <= 3)
     {
     	if(len == 2){puts("2");}
     	else 
     	{
     		if(s[1] != s[2] && s[1] != s[3] && s[2] != s[3])puts("3");
     		else if(s[1] == s[3])puts("7");
     		else puts("6");
     	}
     }
     else 
     {
     	for(int i = 1;i <= len;i++)g = (g + s[i] - 'a') % 3;
     	for(int i = 0;i < 3;i++)f[1][i][i][0] = 1;
     	for(int i = 1;i < len;i++)
     	 for(int j = 0;j < 3;j++)
     	  for(int k = 0;k < 3;k++)
     	   for(int l = 0;l < 2;l++)
     	    for(int t = 0;t < 3;t++)
     	    (f[i + 1][t][(k + t) % 3][l | (t == j)] += f[i][j][k][l]) %= mod;
     	int ret = ((f[len][0][g][1] + f[len][1][g][1]) % mod + f[len][2][g][1]) % mod;
     	printf("%d\n",(ret + notsame()) % mod);
     }
}
```