#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;
const int mod = 998244353;

void add (int &x, int y) {
    x = (x + y) % mod;
}

int dp[N][3][4][2];
string s;
bool a = false, b = false, c = false, adj = false;
set <string> res;

void bt (string s) {
    if (res.find(s) != res.end()) return;
    res.insert(s);

    for (int i = 1; i < s.length(); i++) {
        string t = s;
        if (t[i] != t[i - 1]) {
            if (t[i] == 'a' && t[i - 1] == 'b') t[i] = t[i - 1] = 'c';
            else if (t[i] == 'a' && t[i - 1] == 'c') t[i] = t[i - 1] = 'b';
            else if (t[i] == 'b' && t[i - 1] == 'c') t[i] = t[i - 1] = 'a';
            else if (t[i] == 'b' && t[i - 1] == 'a') t[i] = t[i - 1] = 'c';
            else if (t[i] == 'c' && t[i - 1] == 'a') t[i] = t[i - 1] = 'b';
            else t[i] = t[i - 1] = 'a';
        }
        bt(t);
    }
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> s;
    int sum = 0;
    for (int i = 0; i < s.length(); i++) a |= (s[i] == 'a'), b |= (s[i] == 'b'), c |= (s[i] == 'c'), sum += (s[i] - 'a');
    for (int i = 1; i < s.length(); i++) adj |= (s[i] == s[i - 1]);
    if ((a && !b && !c) || (!a && b && !c) || (!a && !b && c)) return cout << 1, 0;

    if (s.length() <= 3) {
        bt(s);
        cout << res.size();
    }
    else {
        dp[0][0][3][0] = 1;
        for (int i = 0; i < s.length(); i++) {
            for (int j = 0; j < 3; j++) {
                for (int k = 0; k <= 3; k++) {
                    for (int l = 0; l < 2; l++) {
                        if (dp[i][j][k][l]) {
                            for (int m = 0; m < 3; m++) {
                                add(dp[i + 1][(j + m) % 3][m][(k == m) | l], dp[i][j][k][l]);
                            }
                        }
                    }
                }
            }
        }

        int ans = 0;
        for (int i = 0; i < 3; i++) add(ans, dp[s.length()][sum % 3][i][1]);
        cout << ans + (!adj);
    }
    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 namespace std;

const int N = 2e5 + 5;
const int mod = 998244353;

void add (int &x, int y) {
    x = (x + y) % mod;
}

int dp[N][3][4][2];
string s;
bool a = false, b = false, c = false, adj = false;
set <string> res;

void bt (string s) {
    if (res.find(s) != res.end()) return;
    res.insert(s);

    for (int i = 1; i < s.length(); i++) {
        string t = s;
        if (t[i] != t[i - 1]) {
            if (t[i] == 'a' && t[i - 1] == 'b') t[i] = t[i - 1] = 'c';
            else if (t[i] == 'a' && t[i - 1] == 'c') t[i] = t[i - 1] = 'b';
            else if (t[i] == 'b' && t[i - 1] == 'c') t[i] = t[i - 1] = 'a';
            else if (t[i] == 'b' && t[i - 1] == 'a') t[i] = t[i - 1] = 'c';
            else if (t[i] == 'c' && t[i - 1] == 'a') t[i] = t[i - 1] = 'b';
            else t[i] = t[i - 1] = 'a';
        }
        bt(t);
    }
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> s;
    int sum = 0;
    for (int i = 0; i < s.length(); i++) a |= (s[i] == 'a'), b |= (s[i] == 'b'), c |= (s[i] == 'c'), sum += (s[i] - 'a');
    for (int i = 1; i < s.length(); i++) adj |= (s[i] == s[i - 1]);
    if ((a && !b && !c) || (!a && b && !c) || (!a && !b && c)) return cout << 1, 0;

    if (s.length() <= 3) {
        bt(s);
        cout << res.size();
    }
    else {
        dp[0][0][3][0] = 1;
        for (int i = 0; i < s.length(); i++) {
            for (int j = 0; j < 3; j++) {
                for (int k = 0; k <= 3; k++) {
                    for (int l = 0; l < 2; l++) {
                        if (dp[i][j][k][l]) {
                            for (int m = 0; m < 3; m++) {
                                add(dp[i + 1][(j + m) % 3][m][(k == m) | l], dp[i][j][k][l]);
                            }
                        }
                    }
                }
            }
        }

        int ans = 0;
        for (int i = 0; i < 3; i++) add(ans, dp[s.length()][sum % 3][i][1]);
        cout << ans + (!adj);
    }
    return 0;
}

```