#include <bits/stdc++.h>

using std::pair;
using std::vector;
using std::string;

typedef long long ll;
typedef pair<int, int> pii;

#define fst first
#define snd second
#define pb(a) push_back(a)
#define mp(a, b) std::make_pair(a, b)
#define debug(...) fprintf(stderr, __VA_ARGS__)

template <typename T> bool chkmax(T& a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> bool chkmin(T& a, T b) { return a > b ? a = b, 1 : 0; }

const int oo = 0x3f3f3f3f;

string procStatus() {
    std::ifstream t("/proc/self/status");
    return string(std::istreambuf_iterator<char>(t), std::istreambuf_iterator<char>());
}

template <typename T> T read(T& x) {
    int f = 1; x = 0;
    char ch = getchar();
    for(;!isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
    for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
    return x *= f;
}

const int N = 200000;
const int mo = 998244353;

char st[N + 5];
int dp[N + 5][3][3];

int main() {
#ifdef Wearry
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif

    scanf("%s", st);

    int s = st[0] - 'a';
    int len = strlen(st), f0 = 1, f1 = 1;

    for(int i = 1; i < len; ++i) {
        f0 &= (st[i] != st[i-1]);
        f1 &= (st[i] == st[i-1]);
        s = (s + st[i] - 'a') % 3;
    }
    if(f1) { return !puts("1"); }
    if(len == 2) return !puts("2");
    if(s == 0 && len == 3) return !puts("3");

    int ans = 1;
    for(int i = 1; i < len; ++i) ans = 3ll * ans % mo;

    for(int i = 0; i < 3; ++i) dp[0][i][i] = 1;
    for(int i = 1; i < len; ++i) {
        for(int j = 0; j < 3; ++j) {
            for(int k = 0; k < 3; ++k) if(dp[i-1][j][k]) {
                for(int l = 0; l < 3; ++l) if(l != j) {
                    (dp[i][l][(k + l) % 3] += dp[i-1][j][k]) %= mo;
                }
            }
        }
    }

    ans = ans + f0;
    for(int i = 0; i < 3; ++i) ans = (ans - dp[len-1][i][s]) % mo;

    printf("%d\n", (ans + mo) % mo);

    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 std::pair;
using std::vector;
using std::string;

typedef long long ll;
typedef pair<int, int> pii;

#define fst first
#define snd second
#define pb(a) push_back(a)
#define mp(a, b) std::make_pair(a, b)
#define debug(...) fprintf(stderr, __VA_ARGS__)

template <typename T> bool chkmax(T& a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> bool chkmin(T& a, T b) { return a > b ? a = b, 1 : 0; }

const int oo = 0x3f3f3f3f;

string procStatus() {
    std::ifstream t("/proc/self/status");
    return string(std::istreambuf_iterator<char>(t), std::istreambuf_iterator<char>());
}

template <typename T> T read(T& x) {
    int f = 1; x = 0;
    char ch = getchar();
    for(;!isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
    for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
    return x *= f;
}

const int N = 200000;
const int mo = 998244353;

char st[N + 5];
int dp[N + 5][3][3];

int main() {
#ifdef Wearry
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif

    scanf("%s", st);

    int s = st[0] - 'a';
    int len = strlen(st), f0 = 1, f1 = 1;

    for(int i = 1; i < len; ++i) {
        f0 &= (st[i] != st[i-1]);
        f1 &= (st[i] == st[i-1]);
        s = (s + st[i] - 'a') % 3;
    }
    if(f1) { return !puts("1"); }
    if(len == 2) return !puts("2");
    if(s == 0 && len == 3) return !puts("3");

    int ans = 1;
    for(int i = 1; i < len; ++i) ans = 3ll * ans % mo;

    for(int i = 0; i < 3; ++i) dp[0][i][i] = 1;
    for(int i = 1; i < len; ++i) {
        for(int j = 0; j < 3; ++j) {
            for(int k = 0; k < 3; ++k) if(dp[i-1][j][k]) {
                for(int l = 0; l < 3; ++l) if(l != j) {
                    (dp[i][l][(k + l) % 3] += dp[i-1][j][k]) %= mo;
                }
            }
        }
    }

    ans = ans + f0;
    for(int i = 0; i < 3; ++i) ans = (ans - dp[len-1][i][s]) % mo;

    printf("%d\n", (ans + mo) % mo);

    return 0;
}

```