/**
            ▄█▀ ▀█▀ ▄▀▄ █▀ █▄█▄█ ▄▀▄ █▀ ▄█▀
            <⇋⇋⇋⋛∰≓⊂(⌒,_ゝ⌒)⊃≓∰⋛⇋⇋⇋>

    ♔♕♖♗♘♙ ☜❷☞✪ ィℋ६ ≈ ᗫẵℜℵĬŊĞ ✪☜❷☞ ♚♛♜♝♞♟
    ♔♕♖♗♘♙                             ♚♛♜♝♞♟
                ˙·٠•●♥ Ƹ̵̡Ӝ̵̨̄Ʒ ♥●•٠·˙
**/

#include <bits/stdc++.h>

#define sz(s) s.size()
#define pb push_back
#define fr first
#define sc second
#define mk make_pair
#define all(s) s.begin(), s.end()

using namespace std;

const int N = 1e5 + 5;

int fl, sum;
long long dp[ 3 ][ 3 ], nw[ 3 ][ 3 ];
int mod = 998244353;

inline long long pw( int a, int b )
{
    long long res = 1;
    while( b-- )
        res *= a, res %= mod;
    return res % mod;
}

int main()
{
    string s;
    cin >> s;
    for( int i = 1; i < sz(s); i++ )
    {
        if( s[i] != s[0] )
        {
            fl = 1;
            break;
        }
    }
    if( !fl )
    {
        puts("1");
        return 0;
    }
    if( sz( s ) == 2 )
    {
        cout << 2;
        return 0;
    }
    fl = 0;
    if( sz( s ) == 3 )
    {
        if( s[0] == s[2] )
            cout << 7;
        else if( s[0] != s[ 1 ] and s[ 0 ] != s[ 2 ] and s[ 1 ] != s[ 2 ] )
            cout << 3;
        else
            cout << 6;
        return 0;
    }

    dp[ 0 ][ 0 ] = 1;
    dp[ 1 ][ 1 ] = 1;
    dp[ 2 ][ 2 ] = 1;

    for( int i = 0; i < sz(s); i++ )
        sum += s[ i ] - 'a';

    sum %= 3;

    fl = 0;
    for( int i = 1; i < sz(s); i++ )
    {
        memset( nw, 0, sizeof( nw ) );
        if( s[i] == s[i - 1] )
            fl = 1;
        for( int j = 0; j < 3; j++ )
            for( int k = 0; k < 3; k++ )
                for( int f = 0; f < 3; f++ )
                    if( k != f )
                    {
                        nw[ ( j + f ) % 3 ][ f ] += dp[ j ][ k ];
                        nw[ ( j + f ) % 3 ][ f ] %= mod;
                    }

        swap( dp, nw );
    }

    long long ans = pw( 3, sz(s) - 1 );

    for( int i = 0; i < 3; i++ )
        ans -= dp[ sum ][ i ];

    ans += ( fl ? 0 : 1 );

    ans %= mod;

    if( ans < 0 ) ans += mod;

    cout << ans;
}






### 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>

#define sz(s) s.size()
#define pb push_back
#define fr first
#define sc second
#define mk make_pair
#define all(s) s.begin(), s.end()

using namespace std;

const int N = 1e5 + 5;

int fl, sum;
long long dp[ 3 ][ 3 ], nw[ 3 ][ 3 ];
int mod = 998244353;

inline long long pw( int a, int b )
{
    long long res = 1;
    while( b-- )
        res *= a, res %= mod;
    return res % mod;
}

int main()
{
    string s;
    cin >> s;
    for( int i = 1; i < sz(s); i++ )
    {
        if( s[i] != s[0] )
        {
            fl = 1;
            break;
        }
    }
    if( !fl )
    {
        puts("1");
        return 0;
    }
    if( sz( s ) == 2 )
    {
        cout << 2;
        return 0;
    }
    fl = 0;
    if( sz( s ) == 3 )
    {
        if( s[0] == s[2] )
            cout << 7;
        else if( s[0] != s[ 1 ] and s[ 0 ] != s[ 2 ] and s[ 1 ] != s[ 2 ] )
            cout << 3;
        else
            cout << 6;
        return 0;
    }

    dp[ 0 ][ 0 ] = 1;
    dp[ 1 ][ 1 ] = 1;
    dp[ 2 ][ 2 ] = 1;

    for( int i = 0; i < sz(s); i++ )
        sum += s[ i ] - 'a';

    sum %= 3;

    fl = 0;
    for( int i = 1; i < sz(s); i++ )
    {
        memset( nw, 0, sizeof( nw ) );
        if( s[i] == s[i - 1] )
            fl = 1;
        for( int j = 0; j < 3; j++ )
            for( int k = 0; k < 3; k++ )
                for( int f = 0; f < 3; f++ )
                    if( k != f )
                    {
                        nw[ ( j + f ) % 3 ][ f ] += dp[ j ][ k ];
                        nw[ ( j + f ) % 3 ][ f ] %= mod;
                    }

        swap( dp, nw );
    }

    long long ans = pw( 3, sz(s) - 1 );

    for( int i = 0; i < 3; i++ )
        ans -= dp[ sum ][ i ];

    ans += ( fl ? 0 : 1 );

    ans %= mod;

    if( ans < 0 ) ans += mod;

    cout << ans;
}






```