#include <bits/stdc++.h>
using namespace std;

const int64_t MOD = 998244353;
void add(int64_t& a, int64_t b){
    a = (a+b) % MOD;
}
void mul(int64_t& a, int64_t b){
    a = a*b % MOD;
}


int main(){
    string S;
    cin >> S;
    int N = S.size();
    bool uniq = true;
    for(int i=0; i<N; i++) if(S[0] != S[i]) uniq = false;
    if(uniq){
        cout << 1 << endl;
        return 0;
    }

    if(N <= 3){
        set<string> st;
        st.insert(S);
        queue<string> que;
        que.push(S);
        while(que.size()){
            string s = que.front(); que.pop();
            for(int i=0; i<N-1; i++) if(s[i] != s[i+1]){
                char c = 'a';
                while(c == s[i] || c == s[i+1]) c++;
                string s2 = s;
                s2[i] = s2[i+1] = c;
                if(!st.count(s2)){
                    st.insert(s2);
                    que.push(s2);
                }
            }
        }
        cout << st.size() << endl;
        return 0;
    }

    static int64_t dp[200001][4][3][2];
    dp[0][3][0][0] = 1;
    for(int i=0; i<N; i++) for(int p=0; p<4; p++) for(int r=0; r<3; r++) for(int k=0; k<2; k++) for(int a=0; a<3; a++){
        add(dp[i+1][a][(r+a)%3][k|(p==a)], dp[i][p][r][k]);
    }
    int R = 0, dub = 0;
    for(int i=0; i<N; i++){
        R = (R+S[i]-'a') % 3;
        if(i && S[i-1] == S[i]) dub = 1;
    }
    int64_t ans = 1-dub;
    for(int p=0; p<4; p++) add(ans, dp[N][p][R][1]);
    cout << ans << endl;
}
### 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 int64_t MOD = 998244353;
void add(int64_t& a, int64_t b){
    a = (a+b) % MOD;
}
void mul(int64_t& a, int64_t b){
    a = a*b % MOD;
}


int main(){
    string S;
    cin >> S;
    int N = S.size();
    bool uniq = true;
    for(int i=0; i<N; i++) if(S[0] != S[i]) uniq = false;
    if(uniq){
        cout << 1 << endl;
        return 0;
    }

    if(N <= 3){
        set<string> st;
        st.insert(S);
        queue<string> que;
        que.push(S);
        while(que.size()){
            string s = que.front(); que.pop();
            for(int i=0; i<N-1; i++) if(s[i] != s[i+1]){
                char c = 'a';
                while(c == s[i] || c == s[i+1]) c++;
                string s2 = s;
                s2[i] = s2[i+1] = c;
                if(!st.count(s2)){
                    st.insert(s2);
                    que.push(s2);
                }
            }
        }
        cout << st.size() << endl;
        return 0;
    }

    static int64_t dp[200001][4][3][2];
    dp[0][3][0][0] = 1;
    for(int i=0; i<N; i++) for(int p=0; p<4; p++) for(int r=0; r<3; r++) for(int k=0; k<2; k++) for(int a=0; a<3; a++){
        add(dp[i+1][a][(r+a)%3][k|(p==a)], dp[i][p][r][k]);
    }
    int R = 0, dub = 0;
    for(int i=0; i<N; i++){
        R = (R+S[i]-'a') % 3;
        if(i && S[i-1] == S[i]) dub = 1;
    }
    int64_t ans = 1-dub;
    for(int p=0; p<4; p++) add(ans, dp[N][p][R][1]);
    cout << ans << endl;
}
```