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

int main()
{
    string S;
    cin >> S;
    int N = S.size();
    vector<int> Snum(N);
    long long SnumSum = 0;
    long long ans = 1;
    for (int i = 0; i<N; i++)
    {
        if (S[i] == 'a')
            Snum[i] = 0;
        else if (S[i] == 'b')
            Snum[i] = 1;
        else
            Snum[i] = 2;
        SnumSum += Snum[i];
        if (i>0 && Snum[i] == Snum[i-1])
            ans = 0;
    }

    bool allSameFlg = true;
    {
        for (int i = 0; i < N - 1; i++) if(Snum[i] != Snum[i+1])
                allSameFlg = false;
    }
    if (allSameFlg)
    {
        cout << "1\n";
        return 0;
    }

    if (N == 2)
    {
        cout << "2\n";
        return 0;
    }
    if (N == 3)
    {
        if (Snum[0] != Snum[2] && Snum[1] != Snum[2] && Snum[0] != Snum[1])
        {
            cout << "3\n";
            return 0;
        }
    }

    vector<long long> dist_now(5, 0);
    vector<long long> dist_prev;
    dist_now[3] = 1;
    dist_now[1] = 2;
    for (int i = 2; i <= N; i++)
    {
        dist_prev = dist_now;
        dist_now[0] = dist_prev[1] + dist_prev[2];
        dist_now[1] = 2 * dist_prev[3] + dist_prev[4];
        dist_now[2] = dist_prev[0] + dist_prev[2];
        dist_now[3] = dist_prev[4];
        dist_now[4] = dist_prev[0] + dist_prev[1];

        for (int i = 0; i < 5; i++)
            dist_now[i] = dist_now[i] % (998244353 * 2);
    }

    long long power2n1 = 1;
    long long power3n1 = 1;
    for (int i = 0; i<(N-1); i++)
    {
        power2n1 *= 2;
        power3n1 *= 3;
        power2n1 = power2n1 % 998244353;
        power3n1 = power3n1 % 998244353;
    }
    long long subtract = power2n1;
    if (N % 3 == 0) // 面倒
    {
        if (SnumSum % 3 == 0)
        {
            subtract = dist_now[3] + dist_now[4];
        }
        else
        {
            subtract = (dist_now[0] + dist_now[1] + dist_now[2]) / 2;
        }
    }

    ans += power3n1 - subtract;
    while (ans<0) ans += 998244353;
    cout << ans % 998244353 << "\n";
    return 0;
}

### Prompt

Generate a Cpp solution 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;

int main()
{
    string S;
    cin >> S;
    int N = S.size();
    vector<int> Snum(N);
    long long SnumSum = 0;
    long long ans = 1;
    for (int i = 0; i<N; i++)
    {
        if (S[i] == 'a')
            Snum[i] = 0;
        else if (S[i] == 'b')
            Snum[i] = 1;
        else
            Snum[i] = 2;
        SnumSum += Snum[i];
        if (i>0 && Snum[i] == Snum[i-1])
            ans = 0;
    }

    bool allSameFlg = true;
    {
        for (int i = 0; i < N - 1; i++) if(Snum[i] != Snum[i+1])
                allSameFlg = false;
    }
    if (allSameFlg)
    {
        cout << "1\n";
        return 0;
    }

    if (N == 2)
    {
        cout << "2\n";
        return 0;
    }
    if (N == 3)
    {
        if (Snum[0] != Snum[2] && Snum[1] != Snum[2] && Snum[0] != Snum[1])
        {
            cout << "3\n";
            return 0;
        }
    }

    vector<long long> dist_now(5, 0);
    vector<long long> dist_prev;
    dist_now[3] = 1;
    dist_now[1] = 2;
    for (int i = 2; i <= N; i++)
    {
        dist_prev = dist_now;
        dist_now[0] = dist_prev[1] + dist_prev[2];
        dist_now[1] = 2 * dist_prev[3] + dist_prev[4];
        dist_now[2] = dist_prev[0] + dist_prev[2];
        dist_now[3] = dist_prev[4];
        dist_now[4] = dist_prev[0] + dist_prev[1];

        for (int i = 0; i < 5; i++)
            dist_now[i] = dist_now[i] % (998244353 * 2);
    }

    long long power2n1 = 1;
    long long power3n1 = 1;
    for (int i = 0; i<(N-1); i++)
    {
        power2n1 *= 2;
        power3n1 *= 3;
        power2n1 = power2n1 % 998244353;
        power3n1 = power3n1 % 998244353;
    }
    long long subtract = power2n1;
    if (N % 3 == 0) // 面倒
    {
        if (SnumSum % 3 == 0)
        {
            subtract = dist_now[3] + dist_now[4];
        }
        else
        {
            subtract = (dist_now[0] + dist_now[1] + dist_now[2]) / 2;
        }
    }

    ans += power3n1 - subtract;
    while (ans<0) ans += 998244353;
    cout << ans % 998244353 << "\n";
    return 0;
}

```