
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

string S;
ll mod = 998244353;
int cnt = 0;
ll dp[200010][3][3];

ll pow_mod(ll a,ll b)
{
    if(b == 0)return 1;
    ll res = pow_mod(a * a % mod,b / 2);
    if(b & 1)res = res * a % mod;
    return res;
}

int main()
{
    cin >> S;

    int N = S.size();
    for(int i = 0; i < N - 1; i++)if(S[i] == S[i + 1])cnt++;

    if(cnt == N - 1)
    {
        printf("1\n");
        return 0;
    }
    ll all = 1;
    for(int i = 0; i < N; i++)all = (all * 3) % mod;
    ll mem = 1;
    for(int i = 0; i < N - 1; i++)mem = (mem * 2) % mod;
    mem = (mem * 3) % mod;
    if(N % 3)
    {
        ll ans = ((all - mem + mod) % mod * pow_mod(3,mod - 2) + (cnt == 0)) % mod;
        printf("%lld\n",ans);
    }
    else
    {
        dp[1][0][0] = dp[1][1][1] = dp[1][2][2] = 1;
        for(int i = 0; i <= 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;
                        dp[i + 1][(j + l) % 3][l] += dp[i][j][k];
                        dp[i + 1][(j + l) % 3][l] %= mod;
                    }
                }
            }
        }
        ll sum = 0;
        for(int i = 0; i < N; i++)sum = (sum + (S[i] - 'a')) % 3;
        if(sum != 0)
        {
            ll ans = ((all - (dp[N][1][0] * 9) % mod + mod) % mod * pow_mod(3,mod - 2) + (cnt == 0)) % mod;
            printf("%lld\n",ans);
        }
        else
        {
            if(N == 3)
            {
                printf("%d\n",3);
            }
            else
            {
                ll ans = (all * pow_mod(3,mod - 2) % mod - dp[N][0][0] - dp[N][0][1] - dp[N][0][2] + (cnt == 0) + 3 * mod) % mod;
                printf("%lld\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<bits/stdc++.h>
using namespace std;

typedef long long ll;

string S;
ll mod = 998244353;
int cnt = 0;
ll dp[200010][3][3];

ll pow_mod(ll a,ll b)
{
    if(b == 0)return 1;
    ll res = pow_mod(a * a % mod,b / 2);
    if(b & 1)res = res * a % mod;
    return res;
}

int main()
{
    cin >> S;

    int N = S.size();
    for(int i = 0; i < N - 1; i++)if(S[i] == S[i + 1])cnt++;

    if(cnt == N - 1)
    {
        printf("1\n");
        return 0;
    }
    ll all = 1;
    for(int i = 0; i < N; i++)all = (all * 3) % mod;
    ll mem = 1;
    for(int i = 0; i < N - 1; i++)mem = (mem * 2) % mod;
    mem = (mem * 3) % mod;
    if(N % 3)
    {
        ll ans = ((all - mem + mod) % mod * pow_mod(3,mod - 2) + (cnt == 0)) % mod;
        printf("%lld\n",ans);
    }
    else
    {
        dp[1][0][0] = dp[1][1][1] = dp[1][2][2] = 1;
        for(int i = 0; i <= 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;
                        dp[i + 1][(j + l) % 3][l] += dp[i][j][k];
                        dp[i + 1][(j + l) % 3][l] %= mod;
                    }
                }
            }
        }
        ll sum = 0;
        for(int i = 0; i < N; i++)sum = (sum + (S[i] - 'a')) % 3;
        if(sum != 0)
        {
            ll ans = ((all - (dp[N][1][0] * 9) % mod + mod) % mod * pow_mod(3,mod - 2) + (cnt == 0)) % mod;
            printf("%lld\n",ans);
        }
        else
        {
            if(N == 3)
            {
                printf("%d\n",3);
            }
            else
            {
                ll ans = (all * pow_mod(3,mod - 2) % mod - dp[N][0][0] - dp[N][0][1] - dp[N][0][2] + (cnt == 0) + 3 * mod) % mod;
                printf("%lld\n",ans);
            }
        }
    }
    return 0;
}

```