#include <bits/stdc++.h>
using namespace std;
using Int = long long;
int PREP = (cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(9), 0);
//int SEGV = getenv("D") || (exit(system("D= SEGFAULT_SIGNALS=all catchsegv ./prog.exe") >> 8), 0);
const Int MOD = 998244353;
template <class T> void chadd(T &x, T y) { x = (x + y) % MOD; }
Int dp[300000][3][3][2];
int main() {
    string S; cin >> S;
    if (S.size() <= 3) {
        set<string> se;
        stack<string> st;
        se.insert(S); st.push(S);
        while (!st.empty()) {
            auto s = st.top(); st.pop();
            for (int i = 0; i < s.size() - 1; i++) {
                if (s[i + 1] != s[i]) {
                    string t = s;
                    t[i] = t[i + 1] = 'a' ^ 'b' ^ 'c' ^ s[i] ^ s[i + 1];
                    if (se.count(t) == 0) {
                        se.insert(t);
                        st.push(t);
                    }
                }
            }
        }
        cout << se.size() << '\n';
    } else {
        int eql = 0, diff = 0;
        for (int i = 0; i < S.size() - 1; i++) {
            if (S[i] == S[i + 1]) eql++;
            if (S[i] != S[i + 1]) diff++;
        }
        if (diff == 0) {
            cout << 1 << '\n';
        } else {
            dp[1][0][0][0] = dp[1][1][1][0] = dp[1][2][2][0] = 1;
            for (int i = 1; i < S.size(); i++) {
                for (int j = 0; j < 3; j++) {
                    for (int k = 0; k < 3; k++) {
                        for (int l = 0; l < 2; l++) {
                            for (int m = 0; m < 3; m++) {
                                chadd(dp[i + 1][(j + m) % 3][m][min(1, l + (k == m))], dp[i][j][k][l]);
                            }
                        }
                    }
                }
            }
            Int ans = 0, sum = 0;
            for (int i = 0; i < S.size(); i++) {
                sum = (sum + S[i] - 'a') % 3;
            }
            for (int k = 0; k < 3; k++) {
                ans = (ans + dp[S.size()][sum][k][1]) % MOD;
            }
            cout << (ans + (eql == 0)) % MOD << '\n';
        }
    }
    return 0;
}

### Prompt

Please provide a CPP coded solution to the problem described below:

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 Int = long long;
int PREP = (cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(9), 0);
//int SEGV = getenv("D") || (exit(system("D= SEGFAULT_SIGNALS=all catchsegv ./prog.exe") >> 8), 0);
const Int MOD = 998244353;
template <class T> void chadd(T &x, T y) { x = (x + y) % MOD; }
Int dp[300000][3][3][2];
int main() {
    string S; cin >> S;
    if (S.size() <= 3) {
        set<string> se;
        stack<string> st;
        se.insert(S); st.push(S);
        while (!st.empty()) {
            auto s = st.top(); st.pop();
            for (int i = 0; i < s.size() - 1; i++) {
                if (s[i + 1] != s[i]) {
                    string t = s;
                    t[i] = t[i + 1] = 'a' ^ 'b' ^ 'c' ^ s[i] ^ s[i + 1];
                    if (se.count(t) == 0) {
                        se.insert(t);
                        st.push(t);
                    }
                }
            }
        }
        cout << se.size() << '\n';
    } else {
        int eql = 0, diff = 0;
        for (int i = 0; i < S.size() - 1; i++) {
            if (S[i] == S[i + 1]) eql++;
            if (S[i] != S[i + 1]) diff++;
        }
        if (diff == 0) {
            cout << 1 << '\n';
        } else {
            dp[1][0][0][0] = dp[1][1][1][0] = dp[1][2][2][0] = 1;
            for (int i = 1; i < S.size(); i++) {
                for (int j = 0; j < 3; j++) {
                    for (int k = 0; k < 3; k++) {
                        for (int l = 0; l < 2; l++) {
                            for (int m = 0; m < 3; m++) {
                                chadd(dp[i + 1][(j + m) % 3][m][min(1, l + (k == m))], dp[i][j][k][l]);
                            }
                        }
                    }
                }
            }
            Int ans = 0, sum = 0;
            for (int i = 0; i < S.size(); i++) {
                sum = (sum + S[i] - 'a') % 3;
            }
            for (int k = 0; k < 3; k++) {
                ans = (ans + dp[S.size()][sum][k][1]) % MOD;
            }
            cout << (ans + (eql == 0)) % MOD << '\n';
        }
    }
    return 0;
}

```