#include <bits/stdc++.h>
using namespace std;
#define int long long
#define maxn 200050
#define mod 998244353
int n, ans, f[maxn][3][3][2], sum;
char a[maxn];

int read()
{
    int x = 0, k = 1;
    char c; c = getchar();
    while(c < '0' || c > '9') { if(c == '-') k = -1; }
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * k;
}

bool Check()
{
    for(int i = 2; i <= n; i ++) 
        if(a[i] != a[i - 1]) return 0;
    return 1;
}

bool Check2()
{
    for(int i = 2; i <= n; i ++) 
        if(a[i] == a[i - 1]) return 0;
    return 1;
}

void Up(int &x, int y) { x = (x + y) % mod; }
void DP(int i, int j, int k, int p)
{
    for(int q = 0; q <= 2; q ++)
        Up(f[i + 1][q][(q + k) % 3][p | (j == q)], f[i][j][k][p]);
}

signed main()
{
    scanf("%s", a + 1); n = strlen(a + 1);
    if(Check()) { puts("1"); return 0; }
    if(n <= 3)
    {
        if(n == 2) puts("2");
        else 
        {
            if(a[1] != a[2] && a[1] != a[3] && a[2] != a[3]) puts("3");
            else if(a[1] == a[3]) puts("7");
            else puts("6");
        }
        return 0;
    }
    for(int i = 1; i <= n; i ++) sum = (sum + a[i] - 'a') % 3;
    for(int i = 0; i <= 2; i ++) f[1][i][i][0] = 1;
    for(int i = 1; i <= n - 1; i ++)
        for(int j = 0; j <= 2; j ++)
            for(int k = 0; k <= 2; k ++)
                for(int p = 0; p <= 1; p ++)
                    DP(i, j, k, p);
    for(int i = 0; i <= 2; i ++) Up(ans, f[n][i][sum][1]);
    Up(ans, Check2());
    printf("%lld\n", ans);
    return 0;
}
### Prompt

In Cpp, your task is to solve 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 <bits/stdc++.h>
using namespace std;
#define int long long
#define maxn 200050
#define mod 998244353
int n, ans, f[maxn][3][3][2], sum;
char a[maxn];

int read()
{
    int x = 0, k = 1;
    char c; c = getchar();
    while(c < '0' || c > '9') { if(c == '-') k = -1; }
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * k;
}

bool Check()
{
    for(int i = 2; i <= n; i ++) 
        if(a[i] != a[i - 1]) return 0;
    return 1;
}

bool Check2()
{
    for(int i = 2; i <= n; i ++) 
        if(a[i] == a[i - 1]) return 0;
    return 1;
}

void Up(int &x, int y) { x = (x + y) % mod; }
void DP(int i, int j, int k, int p)
{
    for(int q = 0; q <= 2; q ++)
        Up(f[i + 1][q][(q + k) % 3][p | (j == q)], f[i][j][k][p]);
}

signed main()
{
    scanf("%s", a + 1); n = strlen(a + 1);
    if(Check()) { puts("1"); return 0; }
    if(n <= 3)
    {
        if(n == 2) puts("2");
        else 
        {
            if(a[1] != a[2] && a[1] != a[3] && a[2] != a[3]) puts("3");
            else if(a[1] == a[3]) puts("7");
            else puts("6");
        }
        return 0;
    }
    for(int i = 1; i <= n; i ++) sum = (sum + a[i] - 'a') % 3;
    for(int i = 0; i <= 2; i ++) f[1][i][i][0] = 1;
    for(int i = 1; i <= n - 1; i ++)
        for(int j = 0; j <= 2; j ++)
            for(int k = 0; k <= 2; k ++)
                for(int p = 0; p <= 1; p ++)
                    DP(i, j, k, p);
    for(int i = 0; i <= 2; i ++) Up(ans, f[n][i][sum][1]);
    Up(ans, Check2());
    printf("%lld\n", ans);
    return 0;
}
```