#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;

#define SZ(a) ((int)a.size())
#define ALL(a) a.begin(), a.end()
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define fst first
#define snd second

void dout() { cerr << endl; }

template <typename Head, typename... Tail>
void dout(Head H, Tail... T) {
    cerr << H << ' ';
    dout(T...);
}

const int mod = 998244353;

int mul(int a, int b)
{
    return ((ll)a * b) % mod;
}

int sub(int a, int b)
{
    a -= b;
    if (a < 0)
        a += mod;
    return a;
}

int add(int a, int b)
{
    a += b;
    if (a >= mod)
        a -= mod;
    return a;
}

const int maxN = 2e5 + 47;
int dp[maxN][3][3];

int solve(string s)
{
    set<char> ss(ALL(s));
    if (SZ(ss) == 1)
        return 1;
    if (SZ(ss) == 3 && SZ(s) == 3)
        return 3;
    dp[0][0][0] = 1;
    dp[0][1][1] = 1;
    dp[0][2][2] = 1;
    for (int i = 0; i < maxN - 1; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            for (int k = 0; k < 3; k++)
            {
                for (int l = 0; l < 3; l++)
                {
                    if (j != l)
                    {
                        dp[i + 1][l][(k + l) % 3] = add(dp[i + 1][l][(k + l) % 3], dp[i][j][k]);
                    }
                }
            }
        }
    }
    int pw = 1;
    bool bad = true;
    int z = s[0] - 'a';
    for (int i = 1; i < SZ(s); i++)
    {
        z = (z + s[i] - 'a') % 3;
        pw = mul(pw, 3);
        if (s[i] == s[i - 1])
            bad = false;
    }
    int ans = sub(pw, add(add(dp[SZ(s) - 1][0][z], dp[SZ(s) - 1][1][z]), dp[SZ(s) - 1][2][z]));
    if (bad)
        ans = add(ans, 1);
    return ans;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;
    cout << solve(s) << endl;
    return 0;
}
### Prompt

Please create a solution in cpp to 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;
using ll = long long;
using vi = vector<int>;

#define SZ(a) ((int)a.size())
#define ALL(a) a.begin(), a.end()
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define fst first
#define snd second

void dout() { cerr << endl; }

template <typename Head, typename... Tail>
void dout(Head H, Tail... T) {
    cerr << H << ' ';
    dout(T...);
}

const int mod = 998244353;

int mul(int a, int b)
{
    return ((ll)a * b) % mod;
}

int sub(int a, int b)
{
    a -= b;
    if (a < 0)
        a += mod;
    return a;
}

int add(int a, int b)
{
    a += b;
    if (a >= mod)
        a -= mod;
    return a;
}

const int maxN = 2e5 + 47;
int dp[maxN][3][3];

int solve(string s)
{
    set<char> ss(ALL(s));
    if (SZ(ss) == 1)
        return 1;
    if (SZ(ss) == 3 && SZ(s) == 3)
        return 3;
    dp[0][0][0] = 1;
    dp[0][1][1] = 1;
    dp[0][2][2] = 1;
    for (int i = 0; i < maxN - 1; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            for (int k = 0; k < 3; k++)
            {
                for (int l = 0; l < 3; l++)
                {
                    if (j != l)
                    {
                        dp[i + 1][l][(k + l) % 3] = add(dp[i + 1][l][(k + l) % 3], dp[i][j][k]);
                    }
                }
            }
        }
    }
    int pw = 1;
    bool bad = true;
    int z = s[0] - 'a';
    for (int i = 1; i < SZ(s); i++)
    {
        z = (z + s[i] - 'a') % 3;
        pw = mul(pw, 3);
        if (s[i] == s[i - 1])
            bad = false;
    }
    int ans = sub(pw, add(add(dp[SZ(s) - 1][0][z], dp[SZ(s) - 1][1][z]), dp[SZ(s) - 1][2][z]));
    if (bad)
        ans = add(ans, 1);
    return ans;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;
    cout << solve(s) << endl;
    return 0;
}
```