#include<string>
#include<iostream>
using namespace std;

long long mod = 998244353;
int n;
long long dp[200001][3][3][2];


int main(){
    string S;
    cin >> S;
    n = S.length();

    if(n == 2){
        if(S[0] == S[1]){
            cout << 1 << endl;
            return 0;
        }else{
            cout << 2 << endl;
            return 0;
        }
    }

    if(n == 3){
        int cnt[3] = {};
        for(int i = 0; i < 3; i++){
            cnt[S[i] - 'a'] ++;
        }
        if(cnt[0] && cnt[1] && cnt[2]){
            cout << 3 << endl;
            return 0;
        }
        if(cnt[0] == 3 || cnt[1] == 3 || cnt[2] == 3){
            cout << 1 << endl;
            return 0;
        }
        if(S[0] == S[1] || S[1] == S[2]){
            cout << 6 << endl;
            return 0;
        }
        cout << 7 << endl;
        return 0;
    }

    bool is_same_chars = true;
    for(int i = 0; i + 1 < n; i++){
        if(S[i] != S[i+1]){
            is_same_chars = false;
        }
    }
    if(is_same_chars){
        cout << 1 << endl;
        return 0;
    }
    
    for(int c = 0; c < 3; c++){
        dp[1][c][c][0] = 1;
    }

    for(int i = 1; i < n; i++){
        for(int m = 0; m < 3; m++){
            for(int c = 0; c < 3; c++){
                for(int b = 0; b < 2; b++){
                    for(int c_ = 0; c_ < 3; c_++){
                        if(c == c_){
                            dp[i+1][(m+c_)%3][c_][1] += dp[i][m][c][b];
                            dp[i+1][(m+c_)%3][c_][1] %= mod;
                        }else{
                            dp[i+1][(m+c_)%3][c_][b] += dp[i][m][c][b];
                            dp[i+1][(m+c_)%3][c_][b] %= mod;
                        }
                    }
                }
            }
        }
    }

    int m = 0;
    for(int i = 0; i < n; i++){
        m += S[i] - 'a';
        m %= 3;
    }
    bool has_conti = false;
    for(int i = 0; i < n - 1; i++){
        if(S[i] == S[i+1]){
            has_conti = true;
        }
    }
    cout << (dp[n][m][0][1] + dp[n][m][1][1] + dp[n][m][2][1] + (has_conti?0:1)) % mod << endl;
}

### Prompt

Your task is to create 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<string>
#include<iostream>
using namespace std;

long long mod = 998244353;
int n;
long long dp[200001][3][3][2];


int main(){
    string S;
    cin >> S;
    n = S.length();

    if(n == 2){
        if(S[0] == S[1]){
            cout << 1 << endl;
            return 0;
        }else{
            cout << 2 << endl;
            return 0;
        }
    }

    if(n == 3){
        int cnt[3] = {};
        for(int i = 0; i < 3; i++){
            cnt[S[i] - 'a'] ++;
        }
        if(cnt[0] && cnt[1] && cnt[2]){
            cout << 3 << endl;
            return 0;
        }
        if(cnt[0] == 3 || cnt[1] == 3 || cnt[2] == 3){
            cout << 1 << endl;
            return 0;
        }
        if(S[0] == S[1] || S[1] == S[2]){
            cout << 6 << endl;
            return 0;
        }
        cout << 7 << endl;
        return 0;
    }

    bool is_same_chars = true;
    for(int i = 0; i + 1 < n; i++){
        if(S[i] != S[i+1]){
            is_same_chars = false;
        }
    }
    if(is_same_chars){
        cout << 1 << endl;
        return 0;
    }
    
    for(int c = 0; c < 3; c++){
        dp[1][c][c][0] = 1;
    }

    for(int i = 1; i < n; i++){
        for(int m = 0; m < 3; m++){
            for(int c = 0; c < 3; c++){
                for(int b = 0; b < 2; b++){
                    for(int c_ = 0; c_ < 3; c_++){
                        if(c == c_){
                            dp[i+1][(m+c_)%3][c_][1] += dp[i][m][c][b];
                            dp[i+1][(m+c_)%3][c_][1] %= mod;
                        }else{
                            dp[i+1][(m+c_)%3][c_][b] += dp[i][m][c][b];
                            dp[i+1][(m+c_)%3][c_][b] %= mod;
                        }
                    }
                }
            }
        }
    }

    int m = 0;
    for(int i = 0; i < n; i++){
        m += S[i] - 'a';
        m %= 3;
    }
    bool has_conti = false;
    for(int i = 0; i < n - 1; i++){
        if(S[i] == S[i+1]){
            has_conti = true;
        }
    }
    cout << (dp[n][m][0][1] + dp[n][m][1][1] + dp[n][m][2][1] + (has_conti?0:1)) % mod << endl;
}

```