#include<bits/stdc++.h>

using namespace std;

int brute(string& str, int N) {
    unordered_set<string> res;
    queue<string> q;
    res.insert(str);

    q.push(str);

    while (!q.empty()) {
        string cur = q.front(); q.pop();
        string tmp(cur);

        for (int i = 0; i < N-1; i ++) {
            if (cur[i] != cur[i+1]) {
                char a = cur[i], b = cur[i+1];
                char nch = 'a'*'b'*'c'/a/b;
                tmp[i] = nch, tmp[i+1] = nch;

                if (res.find(tmp) == res.end()) {
                    res.insert(tmp);
                    q.push(tmp);
                }

                tmp[i] = a, tmp[i+1] = b;
            }
        }
    }

    return res.size();
}

const int MAX_N = 2e5;
long long dp[MAX_N+1][3][2][3];
const long long MOD = 998244353;

int main(void) {
    ios_base::sync_with_stdio(false), cin.tie(NULL);
    string str; cin >> str;
    int N = (int)str.size();
    int sums = 0;
    char fir = str[0];

    if (N <= 3) {
        cout << brute(str, N) << '\n';
        return 0;
    }


    for (int i = 0; i < N; i ++) {
        if (fir != str[i])
            fir = 0;

        (sums += str[i]-'a') %= 3;
    }

    if (fir != 0) {
        cout << 1 << '\n';
        return 0;
    }

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

    for (int i = 0; i < N-1; i ++) {
        for (int cur = 0; cur < 3; cur ++) {
            for (int nxt = 0; nxt < 3; nxt ++) {
                for (int j = 0; j < 2; j ++) {
                    for (int k = 0; k < 3; k ++) {
                        (dp[i+1][nxt][j?1:(nxt==cur)][(k+nxt)%3]
                            += dp[i][cur][j][k]) %= MOD;
                    }
                }
            }
        }
    }

    long long res = 0;

    for (int i = 0; i < 3; i ++)
        (res += dp[N-1][i][1][sums]) %= MOD;

    res ++;

    for (int i = 0; i < N; i ++) {
        if (str[i] == str[i+1])  {
            res--;
            break;
        }
    }

    res %= MOD;

    cout << res << '\n';



}

### Prompt

Your challenge is to write 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 brute(string& str, int N) {
    unordered_set<string> res;
    queue<string> q;
    res.insert(str);

    q.push(str);

    while (!q.empty()) {
        string cur = q.front(); q.pop();
        string tmp(cur);

        for (int i = 0; i < N-1; i ++) {
            if (cur[i] != cur[i+1]) {
                char a = cur[i], b = cur[i+1];
                char nch = 'a'*'b'*'c'/a/b;
                tmp[i] = nch, tmp[i+1] = nch;

                if (res.find(tmp) == res.end()) {
                    res.insert(tmp);
                    q.push(tmp);
                }

                tmp[i] = a, tmp[i+1] = b;
            }
        }
    }

    return res.size();
}

const int MAX_N = 2e5;
long long dp[MAX_N+1][3][2][3];
const long long MOD = 998244353;

int main(void) {
    ios_base::sync_with_stdio(false), cin.tie(NULL);
    string str; cin >> str;
    int N = (int)str.size();
    int sums = 0;
    char fir = str[0];

    if (N <= 3) {
        cout << brute(str, N) << '\n';
        return 0;
    }


    for (int i = 0; i < N; i ++) {
        if (fir != str[i])
            fir = 0;

        (sums += str[i]-'a') %= 3;
    }

    if (fir != 0) {
        cout << 1 << '\n';
        return 0;
    }

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

    for (int i = 0; i < N-1; i ++) {
        for (int cur = 0; cur < 3; cur ++) {
            for (int nxt = 0; nxt < 3; nxt ++) {
                for (int j = 0; j < 2; j ++) {
                    for (int k = 0; k < 3; k ++) {
                        (dp[i+1][nxt][j?1:(nxt==cur)][(k+nxt)%3]
                            += dp[i][cur][j][k]) %= MOD;
                    }
                }
            }
        }
    }

    long long res = 0;

    for (int i = 0; i < 3; i ++)
        (res += dp[N-1][i][1][sums]) %= MOD;

    res ++;

    for (int i = 0; i < N; i ++) {
        if (str[i] == str[i+1])  {
            res--;
            break;
        }
    }

    res %= MOD;

    cout << res << '\n';



}

```